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
14#include "llvm/Transforms/Scalar/ConstraintElimination.h"
15#include "ScalarOptions.h"
16#include "llvm/ADT/PointerIntPair.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/ScopeExit.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/Statistic.h"
21#include "llvm/Analysis/ConstraintSystem.h"
22#include "llvm/Analysis/GlobalsModRef.h"
23#include "llvm/Analysis/LoopInfo.h"
24#include "llvm/Analysis/MemoryBuiltins.h"
25#include "llvm/Analysis/OptimizationRemarkEmitter.h"
26#include "llvm/Analysis/ScalarEvolution.h"
27#include "llvm/Analysis/ScalarEvolutionExpressions.h"
28#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
29#include "llvm/Analysis/TargetLibraryInfo.h"
30#include "llvm/Analysis/ValueTracking.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"
37#include "llvm/IR/Instructions.h"
38#include "llvm/IR/Module.h"
39#include "llvm/IR/PatternMatch.h"
40#include "llvm/IR/Verifier.h"
41#include "llvm/Pass.h"
42#include "llvm/Support/Debug.h"
43#include "llvm/Support/DebugCounter.h"
44#include "llvm/Support/MathExtras.h"
45#include "llvm/Transforms/Utils/Cloning.h"
46#include "llvm/Transforms/Utils/ValueMapper.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
64static Instruction *getContextInstForUse(Use &U) {
65 Instruction *UserI = cast<Instruction>(Val: U.getUser());
66 if (auto *Phi = dyn_cast<PHINode>(Val: UserI))
67 UserI = Phi->getIncomingBlock(U)->getTerminator();
68 return UserI;
69}
70
71/// Returns the closest program point dominating all uses of \p I.
72static Instruction *findCommonDominatorOfUses(Instruction &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;
80 Instruction *UserI = getContextInstForUse(U);
81 CommonDom =
82 CommonDom ? DT.findNearestCommonDominator(I1: CommonDom, I2: UserI) : UserI;
83 }
84 if (!CommonDom)
85 return &I;
86 // Uses in unreachable blocks are not in the dominator tree.
87 return DT.getNode(BB: 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;
123 ConditionTy Cond;
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&: *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>(Val&: *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;
215 SmallVector<FactOrCheck, 64> WorkList;
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(BBE: BasicBlockEdge(&BB, Succ), BB: 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;
304 SmallVector<DecompEntry, 3> Vars;
305
306 Decomposition(int64_t Offset) : Offset(Offset) {}
307 Decomposition(Value *V) { Vars.emplace_back(Args: 1, Args&: 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(X: Offset, Y: OtherOffset, Result&: 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(OtherOffset: Other.Offset))
321 return true;
322 append_range(C&: Vars, R: 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(Factor: -1))
331 return true;
332 if (add(OtherOffset: Tmp.Offset))
333 return true;
334 append_range(C&: Vars, R&: 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(X: Offset, Y: Factor, Result&: Offset))
342 return true;
343 for (auto &Var : Vars)
344 if (MulOverflow(X: Var.Coefficient, Y: Factor, Result&: 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(Signed: false);
376 // Add Arg > -1 constraints to unsigned system for all function arguments.
377 for (Value *Arg : FunctionArgs)
378 UnsignedCS.addRow(R: {Entry(0, 0), Entry(-1, Value2Index.at(Val: Arg))},
379 NumVars: 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 true if \p V is known to be non-negative, either because the
408 /// signed system implies it or because ValueTracking can prove it.
409 bool isKnownNonNegative(Value *V);
410
411 /// Returns true if \p V is known to be positive, either because the signed
412 /// system implies it or because ValueTracking can prove it.
413 bool isKnownPositive(Value *V);
414
415 void addFact(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
416 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack);
417
418 /// Turn a comparison of the form \p Op0 \p Pred \p Op1 into a vector of
419 /// constraints, using indices from the corresponding constraint system.
420 /// New variables that need to be added to the system are collected in
421 /// \p NewVariables.
422 ConstraintTy getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
423 SmallVectorImpl<Value *> &NewVariables,
424 bool ForceSignedSystem = false);
425
426 /// Turns a comparison of the form \p Op0 \p Pred \p Op1 into a vector of
427 /// constraints using getConstraint. Returns an empty constraint if the result
428 /// cannot be used to query the existing constraint system, e.g. because it
429 /// would require adding new variables. Also tries to convert signed
430 /// predicates to unsigned ones if possible to allow using the unsigned system
431 /// which increases the effectiveness of the signed <-> unsigned transfer
432 /// logic.
433 ConstraintTy getConstraintForSolving(CmpInst::Predicate Pred, Value *Op0,
434 Value *Op1);
435
436 /// Try to add information from \p A \p Pred \p B to the unsigned/signed
437 /// system if \p Pred is signed/unsigned.
438 void transferToOtherSystem(CmpInst::Predicate Pred, Value *A, Value *B,
439 unsigned NumIn, unsigned NumOut,
440 SmallVectorImpl<StackEntry> &DFSInStack);
441
442private:
443 /// Adds facts into constraint system. \p ForceSignedSystem can be set when
444 /// the \p Pred is eq/ne, and signed constraint system is used when it's
445 /// specified.
446 void addFactImpl(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
447 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack,
448 bool ForceSignedSystem);
449
450 /// Try to use the inequality \p A != \p B to tighten a non-strict bound the
451 /// system already implies to the corresponding strict bound.
452 void tightenBoundUsingNe(Value *A, Value *B, unsigned NumIn, unsigned NumOut,
453 SmallVectorImpl<StackEntry> &DFSInStack);
454};
455
456// Variable and constant offsets for a chain of GEPs, with base pointer BasePtr.
457struct OffsetResult {
458 Value *BasePtr;
459 APInt ConstantOffset;
460 SmallMapVector<Value *, APInt, 4> VariableOffsets;
461 GEPNoWrapFlags NW;
462
463 OffsetResult() : BasePtr(nullptr), ConstantOffset(0, uint64_t(0)) {}
464
465 OffsetResult(GEPOperator &GEP, const DataLayout &DL)
466 : BasePtr(GEP.getPointerOperand()), NW(GEP.getNoWrapFlags()) {
467 ConstantOffset = APInt(DL.getIndexTypeSizeInBits(Ty: BasePtr->getType()), 0);
468 }
469};
470} // namespace
471
472// Try to collect variable and constant offsets for \p GEP, partly traversing
473// nested GEPs. Returns an OffsetResult with nullptr as BasePtr of collecting
474// the offset fails.
475static OffsetResult collectOffsets(GEPOperator &GEP, const DataLayout &DL) {
476 OffsetResult Result(GEP, DL);
477 unsigned BitWidth = Result.ConstantOffset.getBitWidth();
478 if (!GEP.collectOffset(DL, BitWidth, VariableOffsets&: Result.VariableOffsets,
479 ConstantOffset&: Result.ConstantOffset))
480 return {};
481
482 // If we have a nested GEP, check if we can combine the constant offset of the
483 // inner GEP with the outer GEP.
484 if (auto *InnerGEP = dyn_cast<GetElementPtrInst>(Val: Result.BasePtr)) {
485 SmallMapVector<Value *, APInt, 4> VariableOffsets2;
486 APInt ConstantOffset2(BitWidth, 0);
487 bool CanCollectInner = InnerGEP->collectOffset(
488 DL, BitWidth, VariableOffsets&: VariableOffsets2, ConstantOffset&: ConstantOffset2);
489 // TODO: Support cases with more than 1 variable offset.
490 if (!CanCollectInner || Result.VariableOffsets.size() > 1 ||
491 VariableOffsets2.size() > 1 ||
492 (Result.VariableOffsets.size() >= 1 && VariableOffsets2.size() >= 1)) {
493 // More than 1 variable index, use outer result.
494 return Result;
495 }
496 // The GEPs' wrap flags do not prevent the sum of the offsets from
497 // sign-wrapping.
498 bool Overflow = false;
499 APInt CombinedOffset =
500 Result.ConstantOffset.sadd_ov(RHS: ConstantOffset2, Overflow);
501 if (Overflow)
502 return Result;
503
504 Result.BasePtr = InnerGEP->getPointerOperand();
505 Result.ConstantOffset = CombinedOffset;
506 if (Result.VariableOffsets.size() == 0 && VariableOffsets2.size() == 1)
507 Result.VariableOffsets = std::move(VariableOffsets2);
508 Result.NW &= InnerGEP->getNoWrapFlags();
509 }
510 return Result;
511}
512
513static Decomposition decompose(Value *V, ConstraintInfo &Info, bool IsSigned,
514 const DataLayout &DL);
515
516static bool canUseSExt(ConstantInt *CI) {
517 const APInt &Val = CI->getValue();
518 return Val.sgt(RHS: MinSignedConstraintValue) && Val.slt(RHS: MaxConstraintValue);
519}
520
521/// Returns true if \p Info implies that \p Op is in \p R, interpreting \p R as
522/// a signed range if \p Signed is set and as an unsigned range otherwise.
523static bool doesHoldInRange(ConstraintInfo &Info, Value *Op,
524 const ConstantRange &R, bool Signed) {
525 if (R.isEmptySet() || (Signed ? R.isSignWrappedSet() : R.isWrappedSet()))
526 return false;
527
528 if (R.isFullSet())
529 return true;
530
531 unsigned BitWidth = R.getBitWidth();
532 APInt Min = Signed ? R.getSignedMin() : R.getUnsignedMin();
533 APInt Max = Signed ? R.getSignedMax() : R.getUnsignedMax();
534 APInt MinVal = Signed ? APInt::getSignedMinValue(numBits: BitWidth)
535 : APInt::getMinValue(numBits: BitWidth);
536 APInt MaxVal = Signed ? APInt::getSignedMaxValue(numBits: BitWidth)
537 : APInt::getMaxValue(numBits: BitWidth);
538 // Replace bound too large to be decomposed by the largest usable one.
539 if (!Signed && Max.uge(RHS: MaxConstraintValue))
540 Max = APInt(BitWidth, MaxConstraintValue - 1);
541
542 Type *Ty = Op->getType();
543 if (Min != MinVal &&
544 !Info.doesHold(Pred: Signed ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE, A: Op,
545 B: ConstantInt::get(Ty, V: Min)))
546 return false;
547 if (Max != MaxVal &&
548 !Info.doesHold(Pred: Signed ? CmpInst::ICMP_SLE : CmpInst::ICMP_ULE, A: Op,
549 B: ConstantInt::get(Ty, V: Max)))
550 return false;
551 return true;
552}
553
554/// Returns true if \p Opcode applied to \p Op0 and \p Op1 with \p NoWrapFlags
555/// is known to not wrap in signed or unsigned, depending on \p Signed.
556static bool isKnownNoWrap(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
557 unsigned NoWrapFlags, ConstraintInfo &Info,
558 bool Signed) {
559 using OBO = OverflowingBinaryOperator;
560
561 if (NoWrapFlags & (Signed ? OBO::NoSignedWrap : OBO::NoUnsignedWrap))
562 return true;
563
564 if (Opcode == Instruction::Sub) {
565 // Op0 - Op1 does not wrap unsigned if Op0 >=u Op1.
566 if (!Signed)
567 return Info.doesHold(Pred: CmpInst::ICMP_UGE, A: Op0, B: Op1);
568
569 // Op0 - Op1 does not wrap signed if 0 <=s Op1 <=s Op0.
570 if (Info.isKnownNonNegative(V: Op1) &&
571 Info.doesHold(Pred: CmpInst::ICMP_SGE, A: Op0, B: Op1))
572 return true;
573 }
574
575 if (!Signed && (NoWrapFlags & OBO::NoSignedWrap) &&
576 (Opcode == Instruction::Shl || Info.isKnownNonNegative(V: Op1)) &&
577 Info.isKnownNonNegative(V: Op0))
578 return true;
579
580 // For a constant Op1, the ranges of Op0 for which the operation does not
581 // wrap are known exactly; check if the systems imply one of them.
582 auto *C = dyn_cast<ConstantInt>(Val: Op1);
583 if (!C)
584 return false;
585
586 return doesHoldInRange(Info, Op: Op0,
587 R: ConstantRange::makeExactNoWrapRegion(
588 BinOp: Opcode, Other: C->getValue(),
589 NoWrapKind: Signed ? OBO::NoSignedWrap : OBO::NoUnsignedWrap),
590 Signed);
591}
592
593/// Returns true if \p V is known to not wrap in signed or unsigned, depending
594/// on \p Signed.
595static bool isKnownNoWrap(Value *V, ConstraintInfo &Info, bool Signed) {
596 if (match(V, P: m_DisjointOr(L: m_Value(), R: m_Value())))
597 return true;
598
599 if (auto *WO = dyn_cast<WithOverflowInst>(Val: V))
600 return isKnownNoWrap(Opcode: WO->getBinaryOp(), Op0: WO->getLHS(), Op1: WO->getRHS(),
601 /*NoWrapFlags=*/0, Info, Signed);
602
603 if (auto *Trunc = dyn_cast<TruncInst>(Val: V)) {
604 if (Signed)
605 return Trunc->hasNoSignedWrap();
606
607 // A trunc nsw only truncates without unsigned wrap if its operand is
608 // non-negative.
609 return Trunc->hasNoUnsignedWrap() ||
610 (Trunc->hasNoSignedWrap() &&
611 Info.isKnownNonNegative(V: Trunc->getOperand(i_nocapture: 0)));
612 }
613
614 auto *BO = dyn_cast<OverflowingBinaryOperator>(Val: V);
615 return BO &&
616 isKnownNoWrap(Opcode: static_cast<Instruction::BinaryOps>(BO->getOpcode()),
617 Op0: BO->getOperand(i_nocapture: 0), Op1: BO->getOperand(i_nocapture: 1),
618 NoWrapFlags: BO->getNoWrapKind(), Info, Signed);
619}
620
621static Decomposition decomposeGEP(GEPOperator &GEP, ConstraintInfo &Info,
622 bool IsSigned, const DataLayout &DL) {
623 // Do not reason about pointers where the index size is larger than 64 bits,
624 // as the coefficients used to encode constraints are 64 bit integers.
625 if (DL.getIndexTypeSizeInBits(Ty: GEP.getPointerOperand()->getType()) > 64)
626 return &GEP;
627
628 assert(!IsSigned && "The logic below only supports decomposition for "
629 "unsigned predicates at the moment.");
630 const auto &[BasePtr, ConstantOffset, VariableOffsets, NW] =
631 collectOffsets(GEP, DL);
632 // We support either plain gep nuw, or gep nusw with non-negative offset,
633 // which implies gep nuw.
634 if (!BasePtr || NW == GEPNoWrapFlags::none())
635 return &GEP;
636
637 // For a nuw-only GEP (nuw without nusw/inbounds), the offset must be
638 // interpreted as unsigned.
639 if (!NW.hasNoUnsignedSignedWrap() && ConstantOffset.isNegative())
640 return &GEP;
641
642 Decomposition Result(ConstantOffset.getSExtValue(), DecompEntry(1, BasePtr));
643 for (auto [Index, Scale] : VariableOffsets) {
644 if (!NW.hasNoUnsignedWrap()) {
645 // Try to prove nuw from nusw and nneg. If the index cannot be proven
646 // non-negative, keep the GEP as-is instead of decomposing it.
647 assert(NW.hasNoUnsignedSignedWrap() && "Must have nusw flag");
648 if (!Info.isKnownNonNegative(V: Index))
649 return &GEP;
650 } else if (!NW.hasNoUnsignedSignedWrap()) {
651 // For a nuw-only GEP, the scale is unsigned and must fit in the signed
652 // coefficient.
653 if (Scale.isNegative())
654 return &GEP;
655 }
656
657 auto IdxResult = decompose(V: Index, Info, IsSigned, DL);
658 if (IdxResult.mul(Factor: Scale.getSExtValue()))
659 return &GEP;
660 if (Result.add(Other: IdxResult))
661 return &GEP;
662 }
663 return Result;
664}
665
666// Decomposes \p V into a constant offset + list of pairs { Coefficient,
667// Variable } where Coefficient * Variable. The sum of the constant offset and
668// pairs equals \p V.
669//
670// Looking through certain expressions is only valid if a pre-condition holds.
671// Pre-conditions are checked against \p Info as needed.
672static Decomposition decomposeImpl(Value *V, ConstraintInfo &Info,
673 bool IsSigned, const DataLayout &DL);
674
675/// Returns true if \p V is an operation decomposeImpl can look through.
676static bool mayLookThrough(Value *V) {
677 auto *Op = dyn_cast<Operator>(Val: V);
678 if (!Op)
679 return false;
680 switch (Op->getOpcode()) {
681 case Instruction::GetElementPtr:
682 case Instruction::Add:
683 case Instruction::Sub:
684 case Instruction::Mul:
685 case Instruction::Shl:
686 case Instruction::ZExt:
687 case Instruction::SExt:
688 case Instruction::Trunc:
689 case Instruction::Or:
690 case Instruction::Xor:
691 return true;
692 default:
693 return false;
694 }
695}
696
697static Decomposition decompose(Value *V, ConstraintInfo &Info, bool IsSigned,
698 const DataLayout &DL) {
699 if (!mayLookThrough(V))
700 return decomposeImpl(V, Info, IsSigned, DL);
701
702 PointerIntPair<Value *, 1, bool> Key(V, IsSigned);
703 auto &Cache = Info.getDecomposeCache();
704 auto It = Cache.find(Val: Key);
705 if (It != Cache.end())
706 return It->second;
707
708 Decomposition Result = decomposeImpl(V, Info, IsSigned, DL);
709 Info.getDecomposeCache().insert(KV: {Key, Result});
710 return Result;
711}
712
713static Decomposition decomposeImpl(Value *V, ConstraintInfo &Info,
714 bool IsSigned, const DataLayout &DL) {
715 auto MergeResults = [&Info, IsSigned,
716 &DL](Value *A, Value *B,
717 bool IsSignedB) -> std::optional<Decomposition> {
718 auto ResA = decompose(V: A, Info, IsSigned, DL);
719 auto ResB = decompose(V: B, Info, IsSigned: IsSignedB, DL);
720 if (ResA.add(Other: ResB))
721 return std::nullopt;
722 return ResA;
723 };
724
725 Type *Ty = V->getType()->getScalarType();
726 if (Ty->isPointerTy() && !IsSigned) {
727 if (auto *GEP = dyn_cast<GEPOperator>(Val: V))
728 return decomposeGEP(GEP&: *GEP, Info, IsSigned, DL);
729 if (isa<ConstantPointerNull>(Val: V))
730 return int64_t(0);
731
732 return V;
733 }
734
735 // Don't handle integers > 64 bit. Our coefficients are 64-bit large, so
736 // coefficient add/mul may wrap, while the operation in the full bit width
737 // would not.
738 if (!Ty->isIntegerTy() || Ty->getIntegerBitWidth() > 64)
739 return V;
740
741 if (auto *CI = dyn_cast<ConstantInt>(Val: V)) {
742 if (IsSigned) {
743 if (canUseSExt(CI))
744 return CI->getSExtValue();
745 } else if (!CI->uge(Num: MaxConstraintValue)) {
746 return int64_t(CI->getZExtValue());
747 }
748 return V;
749 }
750
751 Value *Op0;
752 Value *Op1;
753 ConstantInt *CI;
754
755 if (match(V, P: m_ZExt(Op: m_Value(V&: Op0)))) {
756 // In the signed system, the ZExt must be non-negative.
757 if (IsSigned && !cast<ZExtInst>(Val: V)->hasNonNeg())
758 return V;
759 V = Op0;
760 } else if (match(V, P: m_SExt(Op: m_Value(V&: Op0)))) {
761 // In the unsigned system, the SExt operand must be non-negative.
762 if (!IsSigned && !Info.isKnownNonNegative(V: Op0))
763 return V;
764 V = Op0;
765 } else if (auto *Trunc = dyn_cast<TruncInst>(Val: V)) {
766 if (Trunc->getSrcTy()->getScalarSizeInBits() <= 64 &&
767 isKnownNoWrap(V: Trunc, Info, Signed: IsSigned))
768 V = Trunc->getOperand(i_nocapture: 0);
769 }
770
771 if (match(V, P: m_AddLike(L: m_Value(V&: Op0), R: m_Value(V&: Op1)))) {
772 if (isKnownNoWrap(V, Info, Signed: IsSigned)) {
773 if (auto Decomp = MergeResults(Op0, Op1, IsSigned))
774 return *Decomp;
775 return V;
776 }
777 // In the unsigned system, adding a negative constant only wraps if Op0 is
778 // smaller than it.
779 if (!IsSigned && match(V: Op1, P: m_ConstantInt(CI)) && CI->isNegative() &&
780 canUseSExt(CI) &&
781 Info.doesHold(Pred: CmpInst::ICMP_UGE, A: Op0,
782 B: ConstantInt::get(Ty: Op0->getType(), V: -CI->getSExtValue())))
783 if (auto Decomp = MergeResults(Op0, CI, /*IsSignedB=*/true))
784 return *Decomp;
785 return V;
786 }
787
788 // `xor %x, -1` is equivalent to `sub nsw -1, %x`.
789 if (IsSigned && match(V, P: m_Not(V: m_Value(V&: Op0)))) {
790 Decomposition Result(-1);
791 if (!Result.sub(Other: decompose(V: Op0, Info, IsSigned, DL)))
792 return Result;
793 return V;
794 }
795
796 if (match(V, P: m_Sub(L: m_Value(V&: Op0), R: m_Value(V&: Op1)))) {
797 if (isKnownNoWrap(V, Info, Signed: IsSigned)) {
798 auto ResA = decompose(V: Op0, Info, IsSigned, DL);
799 auto ResB = decompose(V: Op1, Info, IsSigned, DL);
800 if (!ResA.sub(Other: ResB))
801 return ResA;
802 }
803 return V;
804 }
805
806 if (match(V, P: m_Mul(L: m_Value(V&: Op0), R: m_ConstantInt(CI)))) {
807 // A negative constant is only a valid coefficient in the signed system; in
808 // the unsigned system the multiplier is the constant's unsigned value.
809 if (canUseSExt(CI) && (IsSigned || !CI->isNegative()) &&
810 isKnownNoWrap(V, Info, Signed: IsSigned)) {
811 auto Result = decompose(V: Op0, Info, IsSigned, DL);
812 if (!Result.mul(Factor: CI->getSExtValue()))
813 return Result;
814 }
815 return V;
816 }
817
818 if (match(V, P: m_Shl(L: m_Value(V&: Op0), R: m_ConstantInt(CI)))) {
819 // (shl x, shift) is (mul x, 1 << shift). The scale must fit in the signed
820 // coefficient, so reject shifts >= 63. Also reject a shift of bw-1, for
821 // which the product is not representable.
822 int64_t MaxShift = IsSigned ? Ty->getIntegerBitWidth() - 1 : 63;
823 if (!CI->isNegative() && CI->getSExtValue() < MaxShift &&
824 isKnownNoWrap(V, Info, Signed: IsSigned)) {
825 auto Result = decompose(V: Op0, Info, IsSigned, DL);
826 if (!Result.mul(Factor: int64_t{1} << CI->getSExtValue()))
827 return Result;
828 }
829 return V;
830 }
831
832 return V;
833}
834
835/// Build the row for 'ADec <= BDec', using the indices from \p Value2Index.
836/// Variables not in \p Value2Index are appended to \p NewVariables and get the
837/// indices following the ones in \p Value2Index. Returns an empty row if the
838/// coefficients overflow.
839static RowTy getRowForLessEqual(const Decomposition &ADec,
840 const Decomposition &BDec,
841 const DenseMap<Value *, unsigned> &Value2Index,
842 SmallVectorImpl<Value *> &NewVariables) {
843 // Build the row, by first adding all coefficients from A and then subtracting
844 // all coefficients from B.
845 int64_t OffsetSum;
846 if (SubOverflow(X: BDec.Offset, Y: ADec.Offset, Result&: OffsetSum))
847 return {};
848 RowTy R(1, Entry(OffsetSum, 0));
849 auto GetCoefficient = [&R](unsigned Idx) -> int64_t & {
850 // The entry for Idx, or the place to insert it at, is the first entry with
851 // an index >= Idx.
852 Entry *I =
853 find_if(Range: drop_begin(RangeOrContainer&: R), P: [Idx](const Entry &E) { return E.Id >= Idx; });
854 if (I == R.end() || I->Id != Idx)
855 I = R.insert(I, Elt: Entry(0, Idx));
856 return I->Coefficient;
857 };
858 // First try to look up \p V in Value2Index and NewVariables. Otherwise add a
859 // new entry to NewVariables.
860 auto GetOrAddIndex = [&Value2Index, &NewVariables](Value *V) -> unsigned {
861 auto V2I = Value2Index.find(Val: V);
862 if (V2I != Value2Index.end())
863 return V2I->second;
864 unsigned Idx = find(Range&: NewVariables, Val: V) - NewVariables.begin();
865 if (Idx == NewVariables.size())
866 NewVariables.push_back(Elt: V);
867 return Value2Index.size() + Idx + 1;
868 };
869 for (const DecompEntry &KV : ADec.Vars)
870 GetCoefficient(GetOrAddIndex(KV.Variable)) += KV.Coefficient;
871
872 for (const DecompEntry &KV : BDec.Vars) {
873 auto &Coeff = GetCoefficient(GetOrAddIndex(KV.Variable));
874 if (SubOverflow(X: Coeff, Y: KV.Coefficient, Result&: Coeff))
875 return {};
876 }
877
878 // Drop coefficients that cancelled out.
879 erase_if(C&: R, P: [](const Entry &E) { return E.Id != 0 && E.Coefficient == 0; });
880 return R;
881}
882
883ConstraintTy
884ConstraintInfo::getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
885 SmallVectorImpl<Value *> &NewVariables,
886 bool ForceSignedSystem) {
887 assert(NewVariables.empty() && "NewVariables must be empty when passed in");
888 assert((!ForceSignedSystem || CmpInst::isEquality(Pred)) &&
889 "signed system can only be forced on eq/ne");
890
891 bool IsEq = false;
892 bool IsNe = false;
893
894 // Try to convert Pred to one of ULE/ULT/SLE/SLT.
895 switch (Pred) {
896 case CmpInst::ICMP_UGT:
897 case CmpInst::ICMP_UGE:
898 case CmpInst::ICMP_SGT:
899 case CmpInst::ICMP_SGE: {
900 Pred = CmpInst::getSwappedPredicate(pred: Pred);
901 std::swap(a&: Op0, b&: Op1);
902 break;
903 }
904 case CmpInst::ICMP_EQ:
905 if (!ForceSignedSystem && match(V: Op1, P: m_Zero())) {
906 Pred = CmpInst::ICMP_ULE;
907 } else {
908 IsEq = true;
909 Pred = CmpInst::ICMP_ULE;
910 }
911 break;
912 case CmpInst::ICMP_NE:
913 if (!ForceSignedSystem && match(V: Op1, P: m_Zero())) {
914 Pred = CmpInst::getSwappedPredicate(pred: CmpInst::ICMP_UGT);
915 std::swap(a&: Op0, b&: Op1);
916 } else {
917 IsNe = true;
918 Pred = CmpInst::ICMP_ULE;
919 }
920 break;
921 default:
922 break;
923 }
924
925 if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT &&
926 Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT)
927 return {};
928
929 bool IsSigned = ForceSignedSystem || CmpInst::isSigned(Pred);
930 auto &Value2Index = getValue2Index(Signed: IsSigned);
931 auto ADec = decompose(V: Op0->stripPointerCastsSameRepresentation(), Info&: *this,
932 IsSigned, DL);
933 auto BDec = decompose(V: Op1->stripPointerCastsSameRepresentation(), Info&: *this,
934 IsSigned, DL);
935 RowTy R = getRowForLessEqual(ADec, BDec, Value2Index, NewVariables);
936 if (R.empty())
937 return {};
938
939 if (Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_ULT)
940 if (AddOverflow(X: R[0].Coefficient, Y: int64_t(-1), Result&: R[0].Coefficient))
941 return {};
942
943 // Remove any new variable without a coefficient in the row.
944 unsigned NumV2I = Value2Index.size();
945 NewVariables.truncate(N: R.back().Id > NumV2I ? R.back().Id - NumV2I : 0);
946
947 return ConstraintTy(std::move(R), Value2Index.size() + NewVariables.size(),
948 IsSigned, IsEq, IsNe);
949}
950
951ConstraintTy ConstraintInfo::getConstraintForSolving(CmpInst::Predicate Pred,
952 Value *Op0, Value *Op1) {
953 Constant *NullC = Constant::getNullValue(Ty: Op0->getType());
954 // Handle trivially true compares directly to avoid adding V UGE 0 constraints
955 // for all variables in the unsigned system.
956 if ((Pred == CmpInst::ICMP_ULE && Op0 == NullC) ||
957 (Pred == CmpInst::ICMP_UGE && Op1 == NullC)) {
958 // Return constraint that's trivially true.
959 return ConstraintTy(RowTy(1, Entry(0, 0)), /*NumVars=*/0,
960 /*IsSigned=*/false, /*IsEq=*/false, /*IsNe=*/false);
961 }
962
963 // If both operands are known to be non-negative, change signed predicates to
964 // unsigned ones. This increases the reasoning effectiveness in combination
965 // with the signed <-> unsigned transfer logic.
966 if (CmpInst::isSigned(Pred) &&
967 ::isKnownNonNegative(V: Op0, SQ: DL, /*Depth=*/MaxAnalysisRecursionDepth - 1) &&
968 ::isKnownNonNegative(V: Op1, SQ: DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))
969 Pred = ICmpInst::getUnsignedPredicate(Pred);
970
971 SmallVector<Value *> NewVariables;
972 ConstraintTy R = getConstraint(Pred, Op0, Op1, NewVariables);
973 if (!NewVariables.empty())
974 return {};
975 return R;
976}
977
978std::optional<bool>
979ConstraintTy::isImpliedBy(const ConstraintSystem &CS) const {
980 const auto &[SubCS, NewCoefficients] = CS.getSubSystem(R: Coefficients);
981 bool IsConditionImplied = SubCS.isConditionImplied(R: NewCoefficients);
982
983 if (IsEq || IsNe) {
984 auto NegatedOrEqual = ConstraintSystem::negateOrEqual(R: NewCoefficients);
985 bool IsNegatedOrEqualImplied =
986 !NegatedOrEqual.empty() && SubCS.isConditionImplied(R: NegatedOrEqual);
987
988 // In order to check that `%a == %b` is true (equality), both conditions `%a
989 // >= %b` and `%a <= %b` must hold true. When checking for equality (`IsEq`
990 // is true), we return true if they both hold, false in the other cases.
991 if (IsConditionImplied && IsNegatedOrEqualImplied)
992 return IsEq;
993
994 auto Negated = ConstraintSystem::negate(R: NewCoefficients);
995 bool IsNegatedImplied =
996 !Negated.empty() && SubCS.isConditionImplied(R: Negated);
997
998 auto StrictLessThan = ConstraintSystem::toStrictLessThan(R: NewCoefficients);
999 bool IsStrictLessThanImplied =
1000 !StrictLessThan.empty() && SubCS.isConditionImplied(R: StrictLessThan);
1001
1002 // In order to check that `%a != %b` is true (non-equality), either
1003 // condition `%a > %b` or `%a < %b` must hold true. When checking for
1004 // non-equality (`IsNe` is true), we return true if one of the two holds,
1005 // false in the other cases.
1006 if (IsNegatedImplied || IsStrictLessThanImplied)
1007 return IsNe;
1008
1009 return std::nullopt;
1010 }
1011
1012 if (IsConditionImplied)
1013 return true;
1014
1015 auto Negated = ConstraintSystem::negate(R: NewCoefficients);
1016 auto IsNegatedImplied = !Negated.empty() && SubCS.isConditionImplied(R: Negated);
1017 if (IsNegatedImplied)
1018 return false;
1019
1020 // Neither the condition nor its negated holds, did not prove anything.
1021 return std::nullopt;
1022}
1023
1024bool ConstraintInfo::doesHold(CmpInst::Predicate Pred, Value *A, Value *B) {
1025 auto R = getConstraintForSolving(Pred, Op0: A, Op1: B);
1026 return !R.empty() &&
1027 getCS(Signed: R.IsSigned).isConditionImpliedInSubSystem(R: R.Coefficients);
1028}
1029
1030bool ConstraintInfo::isKnownNonNegative(Value *V) {
1031 if (auto *CI = dyn_cast<ConstantInt>(Val: V))
1032 return !CI->isNegative();
1033 return ::isKnownNonNegative(V, SQ: DL) ||
1034 doesHold(Pred: CmpInst::ICMP_SGE, A: V, B: ConstantInt::get(Ty: V->getType(), V: 0));
1035}
1036
1037bool ConstraintInfo::isKnownPositive(Value *V) {
1038 if (auto *CI = dyn_cast<ConstantInt>(Val: V))
1039 return CI->getValue().isStrictlyPositive();
1040 return ::isKnownPositive(V, SQ: DL) ||
1041 doesHold(Pred: CmpInst::ICMP_SGT, A: V, B: ConstantInt::get(Ty: V->getType(), V: 0));
1042}
1043
1044void ConstraintInfo::transferToOtherSystem(
1045 CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
1046 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack) {
1047 // Check if we can combine facts from the signed and unsigned systems to
1048 // derive additional facts.
1049 if (!A->getType()->isIntegerTy())
1050 return;
1051 // FIXME: This currently depends on the order we add facts. Ideally we
1052 // would first add all known facts and only then try to add additional
1053 // facts.
1054 switch (Pred) {
1055 default:
1056 break;
1057 case CmpInst::ICMP_ULT:
1058 case CmpInst::ICMP_ULE:
1059 // If B is a signed positive constant, then A >=s 0 and A <s (or <=s) B.
1060 if (isKnownNonNegative(V: B)) {
1061 addFact(Pred: CmpInst::ICMP_SGE, A, B: ConstantInt::get(Ty: B->getType(), V: 0), NumIn,
1062 NumOut, DFSInStack);
1063 addFact(Pred: ICmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut,
1064 DFSInStack);
1065 }
1066 break;
1067 case CmpInst::ICMP_UGE:
1068 case CmpInst::ICMP_UGT:
1069 // If A is a signed positive constant, then B >=s 0 and A >s (or >=s) B.
1070 if (isKnownNonNegative(V: A)) {
1071 addFact(Pred: CmpInst::ICMP_SGE, A: B, B: ConstantInt::get(Ty: B->getType(), V: 0), NumIn,
1072 NumOut, DFSInStack);
1073 addFact(Pred: ICmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut,
1074 DFSInStack);
1075 }
1076 break;
1077 case CmpInst::ICMP_SLT:
1078 case CmpInst::ICMP_SLE:
1079 if (isKnownNonNegative(V: A))
1080 addFact(Pred: ICmpInst::getUnsignedPredicate(Pred), A, B, NumIn, NumOut,
1081 DFSInStack);
1082 break;
1083 case CmpInst::ICMP_SGT: {
1084 if (doesHold(Pred: CmpInst::ICMP_SGE, A: B, B: Constant::getAllOnesValue(Ty: B->getType())))
1085 addFact(Pred: CmpInst::ICMP_UGE, A, B: ConstantInt::get(Ty: B->getType(), V: 0), NumIn,
1086 NumOut, DFSInStack);
1087 if (isKnownNonNegative(V: B))
1088 addFact(Pred: CmpInst::ICMP_UGT, A, B, NumIn, NumOut, DFSInStack);
1089
1090 break;
1091 }
1092 case CmpInst::ICMP_SGE:
1093 if (isKnownNonNegative(V: B))
1094 addFact(Pred: CmpInst::ICMP_UGE, A, B, NumIn, NumOut, DFSInStack);
1095 break;
1096 }
1097}
1098
1099#ifndef NDEBUG
1100
1101static void dumpConstraint(ArrayRef<Entry> C,
1102 const DenseMap<Value *, unsigned> &Value2Index) {
1103 ConstraintSystem CS(Value2Index);
1104 CS.addRow(C, Value2Index.size());
1105 CS.dump();
1106}
1107#endif
1108
1109/// Splits the induction phi \p PN into the start value, coming from the loop
1110/// predecessor \p LoopPred, and the backedge value, coming from inside the
1111/// loop. Returns {nullptr, nullptr} if \p PN has other incoming values.
1112static std::pair<Value *, Value *>
1113getStartAndBackedgeValue(const PHINode &PN, const BasicBlock *LoopPred) {
1114 assert(PN.getBasicBlockIndex(LoopPred) >= 0 &&
1115 "LoopPred must be a predecessor of the phi's block");
1116 if (PN.getNumIncomingValues() != 2)
1117 return {nullptr, nullptr};
1118 unsigned StartIdx = PN.getIncomingBlock(i: 0) == LoopPred ? 0 : 1;
1119 return {PN.getIncomingValue(i: StartIdx), PN.getIncomingValue(i: 1 - StartIdx)};
1120}
1121
1122/// Matches an increment of \p PhiM by a constant offset, captured in \p Off.
1123/// The increment must be a plain IR add or [u|s]add.with.overflow.
1124template <typename PhiMatchTy>
1125static auto m_IncrementOf(const PhiMatchTy &PhiM, const APInt *&Off) {
1126 return m_CombineOr(
1127 m_c_Add(PhiM, m_APInt(Res&: Off)),
1128 m_ExtractValue<0>(m_CombineOr(
1129 m_c_Intrinsic<Intrinsic::uadd_with_overflow>(PhiM, m_APInt(Res&: Off)),
1130 m_c_Intrinsic<Intrinsic::sadd_with_overflow>(PhiM, m_APInt(Res&: Off)))));
1131}
1132
1133MonotonicInfo State::getMonotonicityInfo(PHINode &PN, Value *Step) {
1134 MonotonicInfo Info;
1135 const APInt *StepOffset = nullptr;
1136 if (match(V: Step, P: m_IncrementOf(PhiM: m_Specific(V: &PN), Off&: StepOffset))) {
1137 Info.Decreasing = StepOffset->isNegative();
1138 if (const auto *Add = dyn_cast<OverflowingBinaryOperator>(Val: Step)) {
1139 Info.Unsigned = !Info.Decreasing && Add->hasNoUnsignedWrap();
1140 Info.Signed = Add->hasNoSignedWrap();
1141 }
1142 } else if (const auto *GEP = dyn_cast<GEPOperator>(Val: Step)) {
1143 // TODO: Handle the non-increasing direction, which needs a nusw GEP with a
1144 // negative constant offset.
1145 const DataLayout &DL = PN.getDataLayout();
1146 APInt GEPOffset(DL.getIndexTypeSizeInBits(Ty: GEP->getType()), 0);
1147 Info.Unsigned = GEP->getPointerOperand() == &PN &&
1148 (GEP->hasNoUnsignedWrap() ||
1149 ((GEP->hasNoUnsignedSignedWrap() &&
1150 GEP->accumulateConstantOffset(DL, Offset&: GEPOffset) &&
1151 !GEPOffset.isNegative())));
1152 }
1153
1154 // Forming the SCEV of a phi is expensive, so only consult it for a PN + C
1155 // step whose no-wrap flags prove nothing.
1156 if (Info.Unsigned || Info.Signed || !StepOffset)
1157 return Info;
1158
1159 const auto *AR = dyn_cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: &PN));
1160 if (!AR)
1161 return Info;
1162 ScalarEvolution::MonotonicPredicateType Expected =
1163 Info.Decreasing ? ScalarEvolution::MonotonicallyDecreasing
1164 : ScalarEvolution::MonotonicallyIncreasing;
1165 auto IsMonotonic = [&](CmpInst::Predicate Pred) {
1166 return SE->getMonotonicPredicateType(LHS: AR, Pred) == Expected;
1167 };
1168 Info.Signed = IsMonotonic(CmpInst::ICMP_SGT);
1169 Info.Unsigned = !Info.Decreasing && IsMonotonic(CmpInst::ICMP_UGT);
1170 return Info;
1171}
1172
1173void State::addBoundsForHeaderInductions(BasicBlock &BB) {
1174 Loop *L = LI.getLoopFor(BB: &BB);
1175 if (!L || L->getHeader() != &BB)
1176 return;
1177 BasicBlock *LoopPred = L->getLoopPredecessor();
1178 if (!LoopPred)
1179 return;
1180
1181 DomTreeNode *DTN = DT.getNode(BB: &BB);
1182 for (PHINode &PN : BB.phis()) {
1183 if (!PN.getType()->isIntegerTy() && !PN.getType()->isPointerTy())
1184 continue;
1185
1186 auto [Start, Step] = getStartAndBackedgeValue(PN, LoopPred);
1187 if (!Start)
1188 continue;
1189
1190 MonotonicInfo Info = getMonotonicityInfo(PN, Step);
1191 // Every variable in the unsigned system already has a `V >= 0` row, so a
1192 // zero start value would just duplicate it.
1193 if (match(V: Start, P: m_Zero()))
1194 Info.Unsigned = false;
1195 if (!Info.Unsigned && !Info.Signed)
1196 continue;
1197
1198 // A non-decreasing induction cannot step below its start value, and a
1199 // non-increasing one cannot step above it.
1200 Value *LHS = &PN, *RHS = Start;
1201 if (Info.Decreasing)
1202 std::swap(a&: LHS, b&: RHS);
1203 CmpPredicate Pred(Info.Unsigned ? CmpInst::ICMP_UGE : CmpInst::ICMP_SGE,
1204 /*HasSameSign=*/Info.Unsigned && Info.Signed);
1205 WorkList.push_back(Elt: FactOrCheck::getConditionFact(DTN, Pred, Op0: LHS, Op1: RHS));
1206 }
1207}
1208
1209void State::addInfoForInductions(BasicBlock &BB) {
1210 auto *L = LI.getLoopFor(BB: &BB);
1211 if (!L)
1212 return;
1213
1214 BasicBlock *Header = L->getHeader();
1215 BasicBlock *Latch = L->getLoopLatch();
1216 if (Header != &BB && Latch != &BB)
1217 return;
1218
1219 // A is either a phi or a post-increment PN + C with constant step. For the
1220 // latter, extract the constant IncStep.
1221 Value *A;
1222 Value *B;
1223 PHINode *PN = nullptr;
1224 const APInt *IncStep = nullptr;
1225 CmpPredicate Pred;
1226 auto IndValue =
1227 m_Value(V&: A, P: m_CombineOr(Ps: m_Phi(PN), Ps: m_IncrementOf(PhiM: m_Phi(PN), Off&: IncStep)));
1228
1229 auto *Br = dyn_cast<CondBrInst>(Val: BB.getTerminator());
1230 if (!Br)
1231 return;
1232
1233 auto CountingCmp = m_c_ICmp(Pred, L: IndValue, R: m_Value(V&: B));
1234 std::optional<bool> PeeledOnEdge;
1235 if (!match(V: Br->getCondition(), P: CountingCmp)) {
1236 // Look through AND/OR, and remember which edge requires all operands to be
1237 // true.
1238 if (match(V: Br->getCondition(), P: m_c_LogicalAnd(L: CountingCmp, R: m_Value())))
1239 PeeledOnEdge = true;
1240 else if (match(V: Br->getCondition(), P: m_c_LogicalOr(L: CountingCmp, R: m_Value())))
1241 PeeledOnEdge = false;
1242 else
1243 return;
1244 }
1245
1246 if (PN->getParent() != Header || PN->getNumIncomingValues() != 2 ||
1247 !SE->isSCEVable(Ty: PN->getType()))
1248 return;
1249
1250 bool ContinueOnTrue =
1251 Pred == CmpInst::ICMP_NE || ICmpInst::isLT(P: Pred) || ICmpInst::isLE(P: Pred);
1252 CmpInst::Predicate ContinuePred =
1253 ContinueOnTrue ? Pred.dropSameSign() : CmpInst::getInversePredicate(pred: Pred);
1254 BasicBlock *InLoopSucc = Br->getSuccessor(i: ContinueOnTrue ? 0 : 1);
1255
1256 // The peeled condition only implies the compare on the edge where the
1257 // combined condition forces its operands, which must be the in-loop edge.
1258 if (PeeledOnEdge && *PeeledOnEdge != ContinueOnTrue)
1259 return;
1260
1261 if (!L->contains(BB: InLoopSucc) || !L->isLoopExiting(BB: &BB))
1262 return;
1263
1264 BasicBlock *LoopPred = L->getLoopPredecessor();
1265 if (!LoopPred || !L->isLoopInvariant(V: B))
1266 return;
1267
1268 auto [StartValue, Backedge] = getStartAndBackedgeValue(PN: *PN, LoopPred);
1269 DomTreeNode *DTN = DT.getNode(BB: InLoopSucc);
1270 DomTreeNode *HeaderDTN = DT.getNode(BB: Header);
1271
1272 // BB is the header or the latch, so every iteration taking the backedge
1273 // checked PN ContinuePred B, which guarantees PN != B for NE and LT
1274 // predicates. For an increment by one, PN != B together with StartValue <= B
1275 // (added precondition) imply PN <= B.
1276 const APInt *Step;
1277 bool HasHeaderBound =
1278 !IncStep && match(V: Backedge, P: m_IncrementOf(PhiM: m_Specific(V: PN), Off&: Step)) &&
1279 Step->isOne() &&
1280 (ContinuePred == CmpInst::ICMP_NE || ICmpInst::isLT(P: ContinuePred));
1281 if (HasHeaderBound) {
1282 for (CmpInst::Predicate BoundPred : {CmpInst::ICMP_ULE, CmpInst::ICMP_SLE})
1283 WorkList.push_back(Elt: FactOrCheck::getConditionFact(
1284 DTN: HeaderDTN, Pred: BoundPred, Op0: PN, Op1: B, Precond: ConditionTy(BoundPred, StartValue, B)));
1285 }
1286
1287 // For latch conditions, we need to inject the condition that holds for the
1288 // next iteration into the header. We limit to post-inc conditions, for which
1289 // an original PN + Step != B condition results in a PN < B constraint in the
1290 // header, which also holds for the next loop iteration. This would no longer
1291 // be correct if the post-inc handling would inject a more precise PN + Step <
1292 // B constraint instead.
1293 if (&BB == Latch && !IncStep)
1294 return;
1295
1296 if (ICmpInst::isRelational(P: ContinuePred)) {
1297 if (A != Backedge)
1298 return;
1299
1300 // The condition ensures ContinuePred holds in the header on each iteration
1301 // other than the first. Together with a precondition on the start value
1302 // (StartValue ContinuePred B), we can add B as bound of PN.
1303 WorkList.push_back(Elt: FactOrCheck::getConditionFact(
1304 DTN: HeaderDTN, Pred: ContinuePred, Op0: PN, Op1: B,
1305 Precond: ConditionTy(ContinuePred, StartValue, B)));
1306
1307 // A signed bound can be translated to the unsigned system if PN is signed
1308 // non-decreasing (StartValue s<= PN s< B) and StartValue u< B holds.
1309 // Then StartValue, PN and B must all have the same sign.
1310 if (ICmpInst::isSigned(Pred: ContinuePred)) {
1311 assert((ContinuePred == CmpInst::ICMP_SLT ||
1312 ContinuePred == CmpInst::ICMP_SLE) &&
1313 "Expected a signed less-than continuation predicate");
1314 MonotonicInfo Info = getMonotonicityInfo(PN&: *PN, Step: Backedge);
1315 if (Info.Signed && !Info.Decreasing) {
1316 CmpInst::Predicate UPred = ICmpInst::getUnsignedPredicate(Pred: ContinuePred);
1317 WorkList.push_back(Elt: FactOrCheck::getConditionFact(
1318 DTN: HeaderDTN, Pred: UPred, Op0: PN, Op1: B, Precond: ConditionTy(UPred, StartValue, B)));
1319 }
1320 }
1321
1322 // A relational latch steps past B rather than landing on it, so none of the
1323 // reasoning below applies.
1324 return;
1325 }
1326
1327 const APInt *StepOffset = nullptr;
1328 const SCEV *StartSCEV = nullptr;
1329 if (match(V: Backedge, P: m_c_Add(L: m_Specific(V: PN), R: m_APInt(Res&: StepOffset)))) {
1330 if (StepOffset->isZero())
1331 return;
1332 } else {
1333 const SCEV *Expr = SE->getSCEV(V: PN);
1334 if (!match(S: Expr,
1335 P: m_scev_AffineAddRec(Op0: m_SCEV(V&: StartSCEV), Op1: m_scev_APInt(C&: StepOffset),
1336 L: m_SpecificLoop(L))))
1337 return;
1338 }
1339
1340 // If we looked through `PN + C`, only derive facts when that add is
1341 // really the induction's post-increment or post-decrement.
1342 if (IncStep && *IncStep != *StepOffset)
1343 return;
1344
1345 MonotonicInfo Info = getMonotonicityInfo(PN&: *PN, Step: Backedge);
1346
1347 // Handle negative steps.
1348 if (StepOffset->isNegative()) {
1349 // TODO: Extend to allow steps > -1.
1350 if (!(-*StepOffset).isOne())
1351 return;
1352
1353 // AR may wrap.
1354 // The loop exits once the compared value reaches B, that is at PN == B when
1355 // comparing the phi, and at PN == B + 1 for a post-decrement. Use
1356 // non-strict predicate for the former, and a strict one for the latter to
1357 // ensure the loop exits before wrapping.
1358 CmpInst::Predicate UPrecond =
1359 IncStep ? CmpInst::ICMP_ULT : CmpInst::ICMP_ULE;
1360 ConditionTy BBeforeStartUnsigned = {UPrecond, B, StartValue};
1361 ConditionTy BBeforeStartSigned = {ICmpInst::getSignedPredicate(Pred: UPrecond), B,
1362 StartValue};
1363
1364 // AR may wrap, so both facts are conditional on B being below StartValue.
1365 // Add StartValue >= PN, which holds as the loop exits before wrapping.
1366 WorkList.push_back(Elt: FactOrCheck::getConditionFact(
1367 DTN, Pred: CmpInst::ICMP_UGE, Op0: StartValue, Op1: PN, Precond: BBeforeStartUnsigned));
1368 if (!(Info.Decreasing && Info.Signed))
1369 WorkList.push_back(Elt: FactOrCheck::getConditionFact(
1370 DTN, Pred: CmpInst::ICMP_SGE, Op0: StartValue, Op1: PN, Precond: BBeforeStartSigned));
1371 // Add PN > B, which holds as the loop exits when reaching B.
1372 WorkList.push_back(Elt: FactOrCheck::getConditionFact(DTN, Pred: CmpInst::ICMP_UGT, Op0: PN,
1373 Op1: B, Precond: BBeforeStartUnsigned));
1374 WorkList.push_back(Elt: FactOrCheck::getConditionFact(DTN, Pred: CmpInst::ICMP_SGT, Op0: PN,
1375 Op1: B, Precond: BBeforeStartSigned));
1376 return;
1377 }
1378
1379 // Make sure AR either steps by 1 or that the value we compare against is a
1380 // GEP based on the same start value and all offsets are a multiple of the
1381 // step size, to guarantee that the induction will reach the value.
1382 if (StepOffset->isZero() || StepOffset->isNegative())
1383 return;
1384
1385 if (!StepOffset->isOne()) {
1386 // Check whether B-Start is known to be a multiple of StepOffset.
1387 if (!StartSCEV)
1388 StartSCEV = SE->getSCEV(V: StartValue);
1389 const SCEV *BMinusStart = SE->getMinusSCEV(LHS: SE->getSCEV(V: B), RHS: StartSCEV);
1390 if (isa<SCEVCouldNotCompute>(Val: BMinusStart) ||
1391 !SE->getConstantMultiple(S: BMinusStart).urem(RHS: *StepOffset).isZero())
1392 return;
1393 }
1394
1395 // We already established that B - Start is a multiple of Step above. The loop
1396 // exits once the compared value reaches B, that is at PN == B when comparing
1397 // the phi, and at PN + Step == B for a post-increment. Together with the
1398 // added precondition StartValue <= B for the former and the strict
1399 // StartValue < B for the latter (which implies StartValue + Step <= B),
1400 // neither PN nor the increment can wrap.
1401 CmpInst::Predicate UPrecond = IncStep ? CmpInst::ICMP_ULT : CmpInst::ICMP_ULE;
1402 ConditionTy StartBeforeBoundUnsigned = {UPrecond, StartValue, B};
1403 ConditionTy StartBeforeBoundSigned = {ICmpInst::getSignedPredicate(Pred: UPrecond),
1404 StartValue, B};
1405
1406 // Add PN >= StartValue, as the loop exits before wrapping.
1407 if (!Info.Unsigned)
1408 WorkList.push_back(Elt: FactOrCheck::getConditionFact(
1409 DTN, Pred: CmpInst::ICMP_UGE, Op0: PN, Op1: StartValue, Precond: StartBeforeBoundUnsigned));
1410 if (!Info.Signed)
1411 WorkList.push_back(Elt: FactOrCheck::getConditionFact(
1412 DTN, Pred: CmpInst::ICMP_SGE, Op0: PN, Op1: StartValue, Precond: StartBeforeBoundSigned));
1413 // Add PN < B, as the loop exits once the compared value reaches B. With a
1414 // header bound, the PN != B condition fact in InLoopSucc already tightens it
1415 // to PN < B.
1416 if (!HasHeaderBound || !canAddSuccessor(BB, Succ: InLoopSucc)) {
1417 WorkList.push_back(Elt: FactOrCheck::getConditionFact(
1418 DTN, Pred: CmpInst::ICMP_SLT, Op0: PN, Op1: B, Precond: StartBeforeBoundSigned));
1419 WorkList.push_back(Elt: FactOrCheck::getConditionFact(
1420 DTN, Pred: CmpInst::ICMP_ULT, Op0: PN, Op1: B, Precond: StartBeforeBoundUnsigned));
1421 }
1422
1423 // Try to add condition from the header or latch to the dedicated exit
1424 // blocks. When exiting either with EQ or NE, we know that the induction value
1425 // must be u<= B, as other exits may only exit earlier.
1426 assert(!StepOffset->isNegative() && "induction must be increasing");
1427 assert(ContinuePred == CmpInst::ICMP_NE && "unsupported predicate");
1428 // The header bound already implies PN u<= B in the exits.
1429 if (HasHeaderBound)
1430 return;
1431 SmallVector<BasicBlock *> ExitBBs;
1432 L->getExitBlocks(ExitBlocks&: ExitBBs);
1433 for (BasicBlock *EB : ExitBBs) {
1434 // Bail out on non-dedicated exits.
1435 if (DT.dominates(A: &BB, B: EB)) {
1436 WorkList.emplace_back(Args: FactOrCheck::getConditionFact(
1437 DTN: DT.getNode(BB: EB), Pred: CmpInst::ICMP_ULE, Op0: A, Op1: B, Precond: StartBeforeBoundUnsigned));
1438 }
1439 }
1440}
1441
1442static bool getConstraintFromMemoryAccess(GetElementPtrInst &GEP,
1443 uint64_t AccessSize,
1444 CmpPredicate &Pred, Value *&A,
1445 Value *&B, const DataLayout &DL,
1446 const TargetLibraryInfo &TLI) {
1447 if (!GEP.hasNoUnsignedWrap())
1448 return false;
1449
1450 Value *Base = GEP.getPointerOperand();
1451 if (auto *InnerGEP = dyn_cast<GetElementPtrInst>(Val: Base))
1452 Base = InnerGEP->getPointerOperand();
1453
1454 ObjectSizeOpts Opts;
1455 // Workaround for gep inbounds, ptr null, idx.
1456 Opts.NullIsUnknownSize = true;
1457 // Be conservative since we are not clear on whether an out of bounds access
1458 // to the padding is UB or not.
1459 Opts.RoundToAlign = true;
1460 std::optional<TypeSize> Size = getBaseObjectSize(Ptr: Base, DL, TLI: &TLI, Opts);
1461 if (!Size || Size->isScalable())
1462 return false;
1463
1464 auto Offset = collectOffsets(GEP&: cast<GEPOperator>(Val&: GEP), DL);
1465 if (Offset.BasePtr != Base || !Offset.NW.hasNoUnsignedWrap())
1466 return false;
1467
1468 if (Offset.VariableOffsets.size() != 1)
1469 return false;
1470
1471 uint64_t BitWidth = Offset.ConstantOffset.getBitWidth();
1472 auto &[Index, Scale] = Offset.VariableOffsets.front();
1473 // Bail out on non-canonical GEPs.
1474 if (Index->getType()->getScalarSizeInBits() != BitWidth)
1475 return false;
1476
1477 // Index * Scale + ConstOffset + AccessSize <= AllocSize
1478 // With nuw flag, we know that the index addition doesn't have unsigned wrap.
1479 // If (AllocSize - (ConstOffset + AccessSize)) wraps around, there is no valid
1480 // value for Index.
1481 APInt MaxIndex = (APInt(BitWidth, Size->getFixedValue() - AccessSize,
1482 /*isSigned=*/false, /*implicitTrunc=*/true) -
1483 Offset.ConstantOffset)
1484 .udiv(RHS: Scale);
1485 Pred = ICmpInst::ICMP_ULE;
1486 A = Index;
1487 B = ConstantInt::get(Ty: Index->getType(), V: MaxIndex);
1488 return true;
1489}
1490
1491/// Returns true if \p I is a candidate whose poison-generating flags may be
1492/// strengthened using the constraint systems.
1493static bool canStrengthenFlags(Instruction *I) {
1494 if (auto *Trunc = dyn_cast<TruncInst>(Val: I))
1495 return Trunc->getType()->isIntegerTy() && Trunc->hasNoSignedWrap() &&
1496 !Trunc->hasNoUnsignedWrap();
1497
1498 auto *BO = dyn_cast<BinaryOperator>(Val: I);
1499 if (!BO || !BO->getType()->isIntegerTy())
1500 return false;
1501
1502 switch (BO->getOpcode()) {
1503 case Instruction::Sub:
1504 if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
1505 return false;
1506 // A - B does not wrap unsigned if A >=u B, and does not wrap signed if
1507 // 0 <=s B <=s A. With a constant B, bounds on A can refine both flags.
1508 return true;
1509 case Instruction::Add:
1510 case Instruction::Mul:
1511 case Instruction::Shl:
1512 if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
1513 return false;
1514 // With a constant second operand, we can use bounds on the first operand to
1515 // refine no-wrap flags. Independently, nuw can be added for nsw if the
1516 // operands are non-negative.
1517 return isa<ConstantInt>(Val: BO->getOperand(i_nocapture: 1)) || BO->hasNoSignedWrap();
1518 default:
1519 return false;
1520 }
1521}
1522
1523/// Try to strengthen \p I's poison generating flags using \p Info. Returns
1524/// true if \p I was modified.
1525static bool tryToStrengthenFlags(Instruction *I, ConstraintInfo &Info) {
1526 assert(canStrengthenFlags(I) && "not a candidate for flag strengthening");
1527
1528 bool Changed = false;
1529 if (!I->hasNoSignedWrap() && isKnownNoWrap(V: I, Info, /*Signed=*/true)) {
1530 LLVM_DEBUG(dbgs() << "Adding nsw to " << *I << "\n");
1531 I->setHasNoSignedWrap();
1532 Changed = true;
1533 }
1534 if (!I->hasNoUnsignedWrap() && isKnownNoWrap(V: I, Info, /*Signed=*/false)) {
1535 LLVM_DEBUG(dbgs() << "Adding nuw to " << *I << "\n");
1536 I->setHasNoUnsignedWrap();
1537 Changed = true;
1538 }
1539 return Changed;
1540}
1541
1542void State::addInfoFor(BasicBlock &BB) {
1543 addBoundsForHeaderInductions(BB);
1544 addInfoForInductions(BB);
1545 auto &DL = BB.getDataLayout();
1546
1547 Value *A, *B;
1548 CmpPredicate Pred;
1549 // True as long as the current instruction is guaranteed to execute.
1550 bool GuaranteedToExecute = true;
1551 // Queue conditions and assumes.
1552 for (Instruction &I : BB) {
1553 if (match(V: &I, P: m_ICmpLike(Pred, L: m_Value(), R: m_Value()))) {
1554 for (Use &U : I.uses()) {
1555 auto *UserI = getContextInstForUse(U);
1556 auto *DTN = DT.getNode(BB: UserI->getParent());
1557 if (!DTN)
1558 continue;
1559 WorkList.push_back(Elt: FactOrCheck::getCheck(DTN, U: &U));
1560 }
1561 continue;
1562 }
1563
1564 auto AddFactFromMemoryAccess = [&](Value *Ptr, Type *AccessType) {
1565 auto *GEP = dyn_cast<GetElementPtrInst>(Val: Ptr);
1566 if (!GEP)
1567 return;
1568 TypeSize AccessSize = DL.getTypeStoreSize(Ty: AccessType);
1569 if (!AccessSize.isFixed())
1570 return;
1571 if (GuaranteedToExecute) {
1572 if (getConstraintFromMemoryAccess(GEP&: *GEP, AccessSize: AccessSize.getFixedValue(),
1573 Pred, A, B, DL, TLI)) {
1574 // The memory access is guaranteed to execute when BB is entered,
1575 // hence the constraint holds on entry to BB.
1576 WorkList.emplace_back(Args: FactOrCheck::getConditionFact(
1577 DTN: DT.getNode(BB: I.getParent()), Pred, Op0: A, Op1: B));
1578 }
1579 } else {
1580 WorkList.emplace_back(
1581 Args: FactOrCheck::getInstFact(DTN: DT.getNode(BB: I.getParent()), Inst: &I));
1582 }
1583 };
1584
1585 if (auto *LI = dyn_cast<LoadInst>(Val: &I)) {
1586 if (!LI->isVolatile())
1587 AddFactFromMemoryAccess(LI->getPointerOperand(), LI->getAccessType());
1588 }
1589 if (auto *SI = dyn_cast<StoreInst>(Val: &I)) {
1590 if (!SI->isVolatile())
1591 AddFactFromMemoryAccess(SI->getPointerOperand(), SI->getAccessType());
1592 }
1593
1594 auto *II = dyn_cast<IntrinsicInst>(Val: &I);
1595 Intrinsic::ID ID = II ? II->getIntrinsicID() : Intrinsic::not_intrinsic;
1596 switch (ID) {
1597 case Intrinsic::assume: {
1598 if (!match(V: I.getOperand(i: 0), P: m_ICmpLike(Pred, L: m_Value(V&: A), R: m_Value(V&: B))))
1599 break;
1600 if (GuaranteedToExecute) {
1601 // The assume is guaranteed to execute when BB is entered, hence Cond
1602 // holds on entry to BB.
1603 WorkList.emplace_back(Args: FactOrCheck::getConditionFact(
1604 DTN: DT.getNode(BB: I.getParent()), Pred, Op0: A, Op1: B));
1605 } else {
1606 WorkList.emplace_back(
1607 Args: FactOrCheck::getInstFact(DTN: DT.getNode(BB: I.getParent()), Inst: &I));
1608 }
1609 break;
1610 }
1611 // Enqueue intrinsics for simplification.
1612 case Intrinsic::uadd_with_overflow:
1613 case Intrinsic::sadd_with_overflow:
1614 case Intrinsic::usub_with_overflow:
1615 case Intrinsic::ssub_with_overflow:
1616 case Intrinsic::umul_with_overflow:
1617 case Intrinsic::smul_with_overflow:
1618 case Intrinsic::ucmp:
1619 case Intrinsic::scmp:
1620 WorkList.push_back(
1621 Elt: FactOrCheck::getCheck(DTN: DT.getNode(BB: &BB), I: cast<CallInst>(Val: &I)));
1622 break;
1623 // Enqueue the intrinsics to add extra info.
1624 case Intrinsic::umin:
1625 case Intrinsic::umax:
1626 case Intrinsic::smin:
1627 case Intrinsic::smax:
1628 case Intrinsic::usub_sat:
1629 // TODO: handle llvm.abs as well
1630 WorkList.push_back(
1631 Elt: FactOrCheck::getCheck(DTN: DT.getNode(BB: &BB), I: cast<CallInst>(Val: &I)));
1632 [[fallthrough]];
1633 case Intrinsic::uadd_sat:
1634 // TODO: Check if it is possible to instead only added the min/max facts
1635 // when simplifying uses of the min/max intrinsics.
1636 if (!isGuaranteedNotToBePoison(V: &I))
1637 break;
1638 [[fallthrough]];
1639 case Intrinsic::abs:
1640 WorkList.push_back(Elt: FactOrCheck::getInstFact(DTN: DT.getNode(BB: &BB), Inst: &I));
1641 break;
1642 }
1643
1644 // Add facts from unsigned division, remainder and logical shift right, and
1645 // from signed division and remainder.
1646 // urem x, n: result < n and result <= x
1647 // udiv x, n: result <= x
1648 // lshr x, n: result <= x
1649 // srem x, n: result >= 0 and result <= x, if x >= 0
1650 // result < n, if n > 0
1651 // sdiv x, n: result >= 0 and result <= x, if x >= 0 and n > 0
1652 // result >= 0 and result < x, if x > 0 and n > 1
1653 if (auto *BO = dyn_cast<BinaryOperator>(Val: &I)) {
1654 if ((BO->getOpcode() == Instruction::URem ||
1655 BO->getOpcode() == Instruction::UDiv ||
1656 BO->getOpcode() == Instruction::LShr ||
1657 BO->getOpcode() == Instruction::SRem ||
1658 BO->getOpcode() == Instruction::SDiv) &&
1659 isGuaranteedNotToBePoison(V: BO))
1660 WorkList.push_back(Elt: FactOrCheck::getInstFact(DTN: DT.getNode(BB: &BB), Inst: BO));
1661 }
1662
1663 // Queue instructions whose flags may be strengthened, checked at the
1664 // closest point dominating all uses.
1665 if (canStrengthenFlags(I: &I)) {
1666 Instruction *CommonDom = findCommonDominatorOfUses(I, DT);
1667 WorkList.push_back(Elt: FactOrCheck::getCheck(
1668 DTN: DT.getNode(BB: CommonDom->getParent()), I: &I, ContextInst: CommonDom));
1669 }
1670
1671 GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(I: &I);
1672 }
1673
1674 if (auto *Switch = dyn_cast<SwitchInst>(Val: BB.getTerminator())) {
1675 for (auto &Case : Switch->cases()) {
1676 BasicBlock *Succ = Case.getCaseSuccessor();
1677 Value *V = Case.getCaseValue();
1678 if (!canAddSuccessor(BB, Succ))
1679 continue;
1680 WorkList.emplace_back(Args: FactOrCheck::getConditionFact(
1681 DTN: DT.getNode(BB: Succ), Pred: CmpInst::ICMP_EQ, Op0: Switch->getCondition(), Op1: V));
1682 }
1683 return;
1684 }
1685
1686 auto *Br = dyn_cast<CondBrInst>(Val: BB.getTerminator());
1687 if (!Br)
1688 return;
1689
1690 Value *Cond = Br->getCondition();
1691
1692 // If the condition is a chain of ORs/AND and the successor only has the
1693 // current block as predecessor, queue conditions for the successor.
1694 Value *Op0, *Op1;
1695 if (match(V: Cond, P: m_LogicalOr(L: m_Value(V&: Op0), R: m_Value(V&: Op1))) ||
1696 match(V: Cond, P: m_LogicalAnd(L: m_Value(V&: Op0), R: m_Value(V&: Op1)))) {
1697 bool IsOr = match(V: Cond, P: m_LogicalOr());
1698 bool IsAnd = match(V: Cond, P: m_LogicalAnd());
1699 // If there's a select that matches both AND and OR, we need to commit to
1700 // one of the options. Arbitrarily pick OR.
1701 if (IsOr && IsAnd)
1702 IsAnd = false;
1703
1704 BasicBlock *Successor = Br->getSuccessor(i: IsOr ? 1 : 0);
1705 if (canAddSuccessor(BB, Succ: Successor)) {
1706 SmallVector<Value *> CondWorkList;
1707 SmallPtrSet<Value *, 8> SeenCond;
1708 auto QueueValue = [&CondWorkList, &SeenCond](Value *V) {
1709 if (SeenCond.insert(Ptr: V).second)
1710 CondWorkList.push_back(Elt: V);
1711 };
1712 QueueValue(Op1);
1713 QueueValue(Op0);
1714 while (!CondWorkList.empty()) {
1715 Value *Cur = CondWorkList.pop_back_val();
1716 if (match(V: Cur, P: m_ICmpLike(Pred, L: m_Value(V&: A), R: m_Value(V&: B)))) {
1717 WorkList.emplace_back(Args: FactOrCheck::getConditionFact(
1718 DTN: DT.getNode(BB: Successor),
1719 Pred: IsOr ? CmpPredicate::getInverse(P: Pred) : Pred, Op0: A, Op1: B));
1720 continue;
1721 }
1722 if (IsOr && match(V: Cur, P: m_LogicalOr(L: m_Value(V&: Op0), R: m_Value(V&: Op1)))) {
1723 QueueValue(Op1);
1724 QueueValue(Op0);
1725 continue;
1726 }
1727 if (IsAnd && match(V: Cur, P: m_LogicalAnd(L: m_Value(V&: Op0), R: m_Value(V&: Op1)))) {
1728 QueueValue(Op1);
1729 QueueValue(Op0);
1730 continue;
1731 }
1732 }
1733 }
1734 return;
1735 }
1736
1737 if (!match(V: Br->getCondition(), P: m_ICmpLike(Pred, L: m_Value(V&: A), R: m_Value(V&: B))))
1738 return;
1739 if (canAddSuccessor(BB, Succ: Br->getSuccessor(i: 0)))
1740 WorkList.emplace_back(Args: FactOrCheck::getConditionFact(
1741 DTN: DT.getNode(BB: Br->getSuccessor(i: 0)), Pred, Op0: A, Op1: B));
1742 if (canAddSuccessor(BB, Succ: Br->getSuccessor(i: 1)))
1743 WorkList.emplace_back(Args: FactOrCheck::getConditionFact(
1744 DTN: DT.getNode(BB: Br->getSuccessor(i: 1)), Pred: CmpPredicate::getInverse(P: Pred), Op0: A, Op1: B));
1745}
1746
1747#ifndef NDEBUG
1748static void dumpUnpackedICmp(raw_ostream &OS, ICmpInst::Predicate Pred,
1749 Value *LHS, Value *RHS) {
1750 OS << "icmp " << Pred << ' ';
1751 LHS->printAsOperand(OS, /*PrintType=*/true);
1752 OS << ", ";
1753 RHS->printAsOperand(OS, /*PrintType=*/false);
1754}
1755#endif
1756
1757namespace {
1758/// Helper to keep track of a condition and if it should be treated as negated
1759/// for reproducer construction.
1760/// Pred == Predicate::BAD_ICMP_PREDICATE indicates that this entry is a
1761/// placeholder to keep the ReproducerCondStack in sync with DFSInStack.
1762struct ReproducerEntry {
1763 ICmpInst::Predicate Pred;
1764 Value *LHS;
1765 Value *RHS;
1766
1767 ReproducerEntry(ICmpInst::Predicate Pred, Value *LHS, Value *RHS)
1768 : Pred(Pred), LHS(LHS), RHS(RHS) {}
1769};
1770} // namespace
1771
1772/// Helper function to generate a reproducer function for simplifying \p Cond.
1773/// The reproducer function contains a series of @llvm.assume calls, one for
1774/// each condition in \p Stack. For each condition, the operand instruction are
1775/// cloned until we reach operands that have an entry in \p Value2Index. Those
1776/// will then be added as function arguments. \p DT is used to order cloned
1777/// instructions. The reproducer function will get added to \p M, if it is
1778/// non-null. Otherwise no reproducer function is generated.
1779static void generateReproducer(Instruction *Cond, bool IsSigned, Module *M,
1780 ArrayRef<ReproducerEntry> Stack,
1781 ConstraintInfo &Info, DominatorTree &DT) {
1782 if (!M)
1783 return;
1784
1785 LLVMContext &Ctx = Cond->getContext();
1786
1787 LLVM_DEBUG(dbgs() << "Creating reproducer for " << *Cond << "\n");
1788
1789 ValueToValueMapTy Old2New;
1790 SmallVector<Value *> Args;
1791 SmallPtrSet<Value *, 8> Seen;
1792 // Traverse Cond and its operands recursively until we reach a value that's in
1793 // Value2Index or not an instruction, or not a operation that
1794 // ConstraintElimination can decompose. Such values will be considered as
1795 // external inputs to the reproducer, they are collected and added as function
1796 // arguments later.
1797 auto CollectArguments = [&](ArrayRef<Value *> Ops, bool IsSigned) {
1798 auto &Value2Index = Info.getValue2Index(Signed: IsSigned);
1799 SmallVector<Value *, 4> WorkList(Ops);
1800 while (!WorkList.empty()) {
1801 Value *V = WorkList.pop_back_val();
1802 if (!Seen.insert(Ptr: V).second)
1803 continue;
1804 if (Old2New.find(Val: V) != Old2New.end())
1805 continue;
1806 if (isa<Constant>(Val: V))
1807 continue;
1808
1809 auto *I = dyn_cast<Instruction>(Val: V);
1810 if (Value2Index.contains(Val: V) || !I ||
1811 !isa<CmpInst, BinaryOperator, GEPOperator, CastInst>(Val: V)) {
1812 Old2New[V] = V;
1813 Args.push_back(Elt: V);
1814 LLVM_DEBUG(dbgs() << " found external input " << *V << "\n");
1815 } else {
1816 append_range(C&: WorkList, R: I->operands());
1817 }
1818 }
1819 };
1820
1821 for (auto &Entry : Stack)
1822 if (Entry.Pred != ICmpInst::BAD_ICMP_PREDICATE)
1823 CollectArguments({Entry.LHS, Entry.RHS}, ICmpInst::isSigned(Pred: Entry.Pred));
1824 CollectArguments(Cond, IsSigned);
1825
1826 SmallVector<Type *> ParamTys;
1827 for (auto *P : Args)
1828 ParamTys.push_back(Elt: P->getType());
1829
1830 FunctionType *FTy = FunctionType::get(Result: Cond->getType(), Params: ParamTys,
1831 /*isVarArg=*/false);
1832 Function *F = Function::Create(Ty: FTy, Linkage: Function::ExternalLinkage,
1833 N: Cond->getModule()->getName() +
1834 Cond->getFunction()->getName() + "repro",
1835 M);
1836 // Add arguments to the reproducer function for each external value collected.
1837 for (unsigned I = 0; I < Args.size(); ++I) {
1838 F->getArg(i: I)->setName(Args[I]->getName());
1839 Old2New[Args[I]] = F->getArg(i: I);
1840 }
1841
1842 BasicBlock *Entry = BasicBlock::Create(Context&: Ctx, Name: "entry", Parent: F);
1843 IRBuilder<> Builder(Entry);
1844 Builder.CreateRet(V: Builder.getTrue());
1845 Builder.SetInsertPoint(Entry->getTerminator());
1846
1847 // Clone instructions in \p Ops and their operands recursively until reaching
1848 // an value in Value2Index (external input to the reproducer). Update Old2New
1849 // mapping for the original and cloned instructions. Sort instructions to
1850 // clone by dominance, then insert the cloned instructions in the function.
1851 auto CloneInstructions = [&](ArrayRef<Value *> Ops, bool IsSigned) {
1852 SmallVector<Value *, 4> WorkList(Ops);
1853 SmallVector<Instruction *> ToClone;
1854 auto &Value2Index = Info.getValue2Index(Signed: IsSigned);
1855 while (!WorkList.empty()) {
1856 Value *V = WorkList.pop_back_val();
1857 if (Old2New.find(Val: V) != Old2New.end())
1858 continue;
1859
1860 auto *I = dyn_cast<Instruction>(Val: V);
1861 if (!Value2Index.contains(Val: V) && I) {
1862 Old2New[V] = nullptr;
1863 ToClone.push_back(Elt: I);
1864 append_range(C&: WorkList, R: I->operands());
1865 }
1866 }
1867
1868 sort(C&: ToClone,
1869 Comp: [&DT](Instruction *A, Instruction *B) { return DT.dominates(Def: A, User: B); });
1870 for (Instruction *I : ToClone) {
1871 Instruction *Cloned = I->clone();
1872 Old2New[I] = Cloned;
1873 Old2New[I]->setName(I->getName());
1874 Cloned->insertBefore(InsertPos: Builder.GetInsertPoint());
1875 Cloned->dropUnknownNonDebugMetadata();
1876 Cloned->setDebugLoc({});
1877 }
1878 };
1879
1880 // Materialize the assumptions for the reproducer using the entries in Stack.
1881 // That is, first clone the operands of the condition recursively until we
1882 // reach an external input to the reproducer and add them to the reproducer
1883 // function. Then add an ICmp for the condition (with the inverse predicate if
1884 // the entry is negated) and an assert using the ICmp.
1885 for (auto &Entry : Stack) {
1886 if (Entry.Pred == ICmpInst::BAD_ICMP_PREDICATE)
1887 continue;
1888
1889 LLVM_DEBUG(dbgs() << " Materializing assumption ";
1890 dumpUnpackedICmp(dbgs(), Entry.Pred, Entry.LHS, Entry.RHS);
1891 dbgs() << "\n");
1892 CloneInstructions({Entry.LHS, Entry.RHS}, CmpInst::isSigned(Pred: Entry.Pred));
1893
1894 auto *Cmp = Builder.CreateICmp(P: Entry.Pred, LHS: Entry.LHS, RHS: Entry.RHS);
1895 Builder.CreateAssumption(Cond: Cmp);
1896 }
1897
1898 // Finally, clone the condition to reproduce and remap instruction operands in
1899 // the reproducer using Old2New.
1900 CloneInstructions(Cond, IsSigned);
1901 Entry->getTerminator()->setOperand(i: 0, Val: Cond);
1902 remapInstructionsInBlocks(Blocks: {Entry}, VMap&: Old2New);
1903
1904 assert(!verifyFunction(*F, &dbgs()));
1905}
1906
1907/// If \p V is a variable in the system and constraint \p C does not contain \p
1908/// V, we managed to decompose \p V at this point, but likely not earlier when
1909/// the fact involving \p V was added. In that case, return a new row for
1910/// V <= decompose(V) to link the variable with the decomposition result.
1911static RowTy getDecompositionLinkRow(Value *V, const ConstraintTy &C,
1912 ConstraintInfo &Info,
1913 const DataLayout &DL) {
1914 const auto &Value2Index = Info.getValue2Index(Signed: C.IsSigned);
1915 auto It = Value2Index.find(Val: V);
1916 if (It == Value2Index.end() ||
1917 any_of(Range: C.Coefficients,
1918 P: [Id = It->second](const Entry &E) { return E.Id == Id; }))
1919 return {};
1920
1921 SmallVector<Value *> NewVariables;
1922 RowTy Row =
1923 getRowForLessEqual(ADec: Decomposition(V), BDec: decompose(V, Info, IsSigned: C.IsSigned, DL),
1924 Value2Index, NewVariables);
1925 return NewVariables.empty() ? Row : RowTy();
1926}
1927
1928static std::optional<bool> checkCondition(CmpInst::Predicate Pred, Value *A,
1929 Value *B, Instruction *CheckInst,
1930 ConstraintInfo &Info) {
1931 LLVM_DEBUG(dbgs() << "Checking " << *CheckInst << "\n");
1932
1933 auto TryWithConstraint = [&](const ConstraintTy &R) -> std::optional<bool> {
1934 if (R.empty()) {
1935 LLVM_DEBUG(dbgs() << " failed to decompose condition\n");
1936 return std::nullopt;
1937 }
1938
1939 auto &CSToUse = Info.getCS(Signed: R.IsSigned);
1940 if (auto ImpliedCondition = R.isImpliedBy(CS: CSToUse)) {
1941 if (!DebugCounter::shouldExecute(Counter&: EliminatedCounter))
1942 return std::nullopt;
1943 LLVM_DEBUG({
1944 dbgs() << "Condition ";
1945 dumpUnpackedICmp(dbgs(),
1946 *ImpliedCondition ? Pred
1947 : CmpInst::getInversePredicate(Pred),
1948 A, B);
1949 dbgs() << " implied by dominating constraints\n";
1950 CSToUse.dump();
1951 });
1952 return ImpliedCondition;
1953 }
1954 return std::nullopt;
1955 };
1956
1957 // Retry the query after adding additional facts for A == decompose(A) and B
1958 // == decompose(B), if needed.
1959 auto TryWithLinkedDecomposition =
1960 [&](const ConstraintTy &C) -> std::optional<bool> {
1961 if (C.empty())
1962 return std::nullopt;
1963
1964 auto &CS = Info.getCS(Signed: C.IsSigned);
1965 unsigned NumVars = Info.getValue2Index(Signed: C.IsSigned).size();
1966 unsigned NumPushed = 0;
1967 for (Value *V : {A, B}) {
1968 RowTy Row =
1969 getDecompositionLinkRow(V, C, Info, DL: CheckInst->getDataLayout());
1970 RowTy Negated = ConstraintSystem::negateOrEqual(R: Row);
1971 if (Row.empty() || Negated.empty())
1972 continue;
1973 NumPushed += CS.addRow(R: Row, NumVars);
1974 NumPushed += CS.addRow(R: Negated, NumVars);
1975 }
1976 if (NumPushed == 0)
1977 return std::nullopt;
1978
1979 std::optional<bool> Res = TryWithConstraint(C);
1980 while (NumPushed--)
1981 CS.popLastConstraint();
1982 return Res;
1983 };
1984
1985 auto R = Info.getConstraintForSolving(Pred, Op0: A, Op1: B);
1986 if (auto ImpliedCondition = TryWithConstraint(R))
1987 return ImpliedCondition;
1988 if (auto ImpliedCondition = TryWithLinkedDecomposition(R))
1989 return ImpliedCondition;
1990
1991 // For non-negative operands unsigned queries can also be checked against the
1992 // signed system.
1993 if (CmpInst::isUnsigned(Pred) && A->getType()->isIntegerTy()) {
1994 SmallVector<Value *> NewVariables;
1995 auto SR = Info.getConstraint(Pred: ICmpInst::getSignedPredicate(Pred), Op0: A, Op1: B,
1996 NewVariables);
1997 if (NewVariables.empty() && !SR.empty() && Info.isKnownNonNegative(V: A) &&
1998 Info.isKnownNonNegative(V: B))
1999 if (auto ImpliedCondition = TryWithConstraint(SR))
2000 return ImpliedCondition;
2001 }
2002
2003 // Additionally, query the signed system for eq/ne predicates if we know about
2004 // A or B.
2005 if (CmpInst::isEquality(pred: Pred)) {
2006 const auto &Value2Index = Info.getValue2Index(/*Signed=*/true);
2007 if (!Value2Index.contains(Val: A) && !Value2Index.contains(Val: B))
2008 return std::nullopt;
2009
2010 SmallVector<Value *> NewVariables;
2011 auto SR = Info.getConstraint(Pred, Op0: A, Op1: B, NewVariables,
2012 /*ForceSignedSystem=*/true);
2013 if (NewVariables.empty()) {
2014 if (auto ImpliedCondition = TryWithConstraint(SR))
2015 return ImpliedCondition;
2016 if (auto ImpliedCondition = TryWithLinkedDecomposition(SR))
2017 return ImpliedCondition;
2018 }
2019 }
2020 return std::nullopt;
2021}
2022
2023static bool checkAndReplaceCondition(
2024 CmpPredicate Pred, Value *A, Value *B, Instruction *CheckInst,
2025 ConstraintInfo &Info, unsigned NumIn, unsigned NumOut,
2026 Instruction *ContextInst, Module *ReproducerModule,
2027 ArrayRef<ReproducerEntry> ReproducerCondStack, DominatorTree &DT,
2028 SmallVectorImpl<Instruction *> &ToRemove) {
2029 auto ReplaceCmpWithConstant = [&](Instruction *CheckInst, bool IsTrue) {
2030 generateReproducer(Cond: CheckInst, IsSigned: ICmpInst::isSigned(Pred), M: ReproducerModule,
2031 Stack: ReproducerCondStack, Info, DT);
2032 Constant *ConstantC = ConstantInt::getBool(
2033 Ty: CmpInst::makeCmpResultType(opnd_type: CheckInst->getType()), V: IsTrue);
2034 bool Changed = CheckInst->replaceUsesWithIf(New: ConstantC, ShouldReplace: [&](Use &U) {
2035 auto *UserI = getContextInstForUse(U);
2036 auto *DTN = DT.getNode(BB: UserI->getParent());
2037 if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut)
2038 return false;
2039 if (UserI->getParent() == ContextInst->getParent() &&
2040 UserI->comesBefore(Other: ContextInst))
2041 return false;
2042
2043 // Conditions in an assume trivially simplify to true. Skip uses
2044 // in assume calls to not destroy the available information.
2045 auto *II = dyn_cast<IntrinsicInst>(Val: U.getUser());
2046 return !II || II->getIntrinsicID() != Intrinsic::assume;
2047 });
2048 NumCondsRemoved++;
2049
2050 // Update the debug value records that satisfy the same condition used
2051 // in replaceUsesWithIf.
2052 SmallVector<DbgVariableRecord *> DVRUsers;
2053 findDbgUsers(V: CheckInst, DbgVariableRecords&: DVRUsers);
2054
2055 for (auto *DVR : DVRUsers) {
2056 auto *DTN = DT.getNode(BB: DVR->getParent());
2057 if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut)
2058 continue;
2059
2060 auto *MarkedI = DVR->getInstruction();
2061 if (MarkedI->getParent() == ContextInst->getParent() &&
2062 MarkedI->comesBefore(Other: ContextInst))
2063 continue;
2064
2065 DVR->replaceVariableLocationOp(OldValue: CheckInst, NewValue: ConstantC);
2066 }
2067
2068 if (CheckInst->use_empty())
2069 ToRemove.push_back(Elt: CheckInst);
2070
2071 return Changed;
2072 };
2073
2074 if (auto ImpliedCondition = checkCondition(Pred, A, B, CheckInst, Info))
2075 return ReplaceCmpWithConstant(CheckInst, *ImpliedCondition);
2076
2077 // When the predicate is samesign and unsigned, we can also make use of the
2078 // signed predicate information.
2079 if (Pred.hasSameSign() && ICmpInst::isUnsigned(Pred))
2080 if (auto ImpliedCondition = checkCondition(
2081 Pred: ICmpInst::getSignedPredicate(Pred), A, B, CheckInst, Info))
2082 return ReplaceCmpWithConstant(CheckInst, *ImpliedCondition);
2083
2084 return false;
2085}
2086
2087static bool checkAndReplaceMinMax(MinMaxIntrinsic *MinMax, ConstraintInfo &Info,
2088 SmallVectorImpl<Instruction *> &ToRemove) {
2089 auto ReplaceMinMaxWithOperand = [&](MinMaxIntrinsic *MinMax, bool UseLHS) {
2090 // TODO: generate reproducer for min/max.
2091 MinMax->replaceAllUsesWith(V: MinMax->getOperand(i_nocapture: UseLHS ? 0 : 1));
2092 ToRemove.push_back(Elt: MinMax);
2093 return true;
2094 };
2095
2096 ICmpInst::Predicate Pred =
2097 ICmpInst::getNonStrictPredicate(pred: MinMax->getPredicate());
2098 if (auto ImpliedCondition = checkCondition(
2099 Pred, A: MinMax->getOperand(i_nocapture: 0), B: MinMax->getOperand(i_nocapture: 1), CheckInst: MinMax, Info))
2100 return ReplaceMinMaxWithOperand(MinMax, *ImpliedCondition);
2101 if (auto ImpliedCondition = checkCondition(
2102 Pred, A: MinMax->getOperand(i_nocapture: 1), B: MinMax->getOperand(i_nocapture: 0), CheckInst: MinMax, Info))
2103 return ReplaceMinMaxWithOperand(MinMax, !*ImpliedCondition);
2104 return false;
2105}
2106
2107static bool checkAndReplaceCmp(CmpIntrinsic *I, ConstraintInfo &Info,
2108 SmallVectorImpl<Instruction *> &ToRemove) {
2109 Value *LHS = I->getOperand(i_nocapture: 0);
2110 Value *RHS = I->getOperand(i_nocapture: 1);
2111 if (checkCondition(Pred: I->getGTPredicate(), A: LHS, B: RHS, CheckInst: I, Info).value_or(u: false)) {
2112 I->replaceAllUsesWith(V: ConstantInt::get(Ty: I->getType(), V: 1));
2113 ToRemove.push_back(Elt: I);
2114 return true;
2115 }
2116 if (checkCondition(Pred: I->getLTPredicate(), A: LHS, B: RHS, CheckInst: I, Info).value_or(u: false)) {
2117 I->replaceAllUsesWith(V: ConstantInt::getSigned(Ty: I->getType(), V: -1));
2118 ToRemove.push_back(Elt: I);
2119 return true;
2120 }
2121 if (checkCondition(Pred: ICmpInst::ICMP_EQ, A: LHS, B: RHS, CheckInst: I, Info).value_or(u: false)) {
2122 I->replaceAllUsesWith(V: ConstantInt::get(Ty: I->getType(), V: 0));
2123 ToRemove.push_back(Elt: I);
2124 return true;
2125 }
2126 return false;
2127}
2128
2129/// Try to replace \p USub by a plain subtract, if \p Info proves it cannot
2130/// saturate. Returns true if \p USub was replaced.
2131static bool checkAndReplaceUSubSat(SaturatingInst *USub, ConstraintInfo &Info,
2132 SmallVectorImpl<Instruction *> &ToRemove) {
2133 // usub.sat(A, B) is A - B exactly when A >=u B.
2134 Value *A = USub->getLHS();
2135 Value *B = USub->getRHS();
2136 if (!checkCondition(Pred: CmpInst::ICMP_UGE, A, B, CheckInst: USub, Info).value_or(u: false))
2137 return false;
2138
2139 IRBuilder<> Builder(USub);
2140 Value *Sub = Builder.CreateSub(LHS: A, RHS: B, Name: "", /*HasNUW=*/true,
2141 /*HasNSW=*/Info.isKnownNonNegative(V: A));
2142 USub->replaceAllUsesWith(V: Sub);
2143 Sub->takeName(V: USub);
2144 ToRemove.push_back(Elt: USub);
2145 return true;
2146}
2147
2148static void
2149removeEntryFromStack(const StackEntry &E, ConstraintInfo &Info,
2150 Module *ReproducerModule,
2151 SmallVectorImpl<ReproducerEntry> &ReproducerCondStack,
2152 SmallVectorImpl<StackEntry> &DFSInStack) {
2153 Info.getDecomposeCache().clear();
2154 Info.popLastConstraint(Signed: E.IsSigned);
2155 // Remove variables in the system that went out of scope.
2156 auto &Mapping = Info.getValue2Index(Signed: E.IsSigned);
2157 for (Value *V : E.ValuesToRelease)
2158 Mapping.erase(Val: V);
2159 Info.popLastNVariables(Signed: E.IsSigned, N: E.ValuesToRelease.size());
2160 DFSInStack.pop_back();
2161 if (ReproducerModule)
2162 ReproducerCondStack.pop_back();
2163}
2164
2165/// Check if either the first condition of an AND or OR is implied by the
2166/// (negated in case of OR) second condition or vice versa.
2167static bool checkOrAndOpImpliedByOther(
2168 FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule,
2169 SmallVectorImpl<ReproducerEntry> &ReproducerCondStack,
2170 SmallVectorImpl<StackEntry> &DFSInStack,
2171 SmallVectorImpl<Instruction *> &ToRemove) {
2172 Instruction *JoinOp = CB.getContextInst();
2173 if (JoinOp->use_empty())
2174 return false;
2175
2176 Instruction *CmpToCheck = cast<Instruction>(Val: CB.getInstructionToSimplify());
2177 unsigned OtherOpIdx = JoinOp->getOperand(i: 0) == CmpToCheck ? 1 : 0;
2178
2179 // Don't try to simplify the first condition of a select by the second, as
2180 // this may make the select more poisonous than the original one.
2181 // TODO: check if the first operand may be poison.
2182 if (OtherOpIdx != 0 && isa<SelectInst>(Val: JoinOp))
2183 return false;
2184
2185 unsigned OldSize = DFSInStack.size();
2186 llvm::scope_exit InfoRestorer([&]() {
2187 // Remove entries again.
2188 while (OldSize < DFSInStack.size()) {
2189 StackEntry E = DFSInStack.back();
2190 removeEntryFromStack(E, Info, ReproducerModule, ReproducerCondStack,
2191 DFSInStack);
2192 }
2193 });
2194 bool IsOr = match(V: JoinOp, P: m_LogicalOr());
2195 SmallVector<Value *, 4> Worklist({JoinOp->getOperand(i: OtherOpIdx)});
2196 // Do a traversal of the AND/OR tree to add facts from leaf compares.
2197 while (!Worklist.empty()) {
2198 Value *Val = Worklist.pop_back_val();
2199 Value *LHS, *RHS;
2200 CmpPredicate Pred;
2201 if (match(V: Val, P: m_ICmpLike(Pred, L: m_Value(V&: LHS), R: m_Value(V&: RHS)))) {
2202 // For OR, check if the negated condition implies CmpToCheck.
2203 if (IsOr)
2204 Pred = CmpInst::getInversePredicate(pred: Pred);
2205 // Optimistically add fact from the other compares in the AND/OR.
2206 Info.addFact(Pred, A: LHS, B: RHS, NumIn: CB.NumIn, NumOut: CB.NumOut, DFSInStack);
2207 continue;
2208 }
2209 if (IsOr ? match(V: Val, P: m_LogicalOr(L: m_Value(V&: LHS), R: m_Value(V&: RHS)))
2210 : match(V: Val, P: m_LogicalAnd(L: m_Value(V&: LHS), R: m_Value(V&: RHS)))) {
2211 Worklist.push_back(Elt: LHS);
2212 Worklist.push_back(Elt: RHS);
2213 }
2214 }
2215 if (OldSize == DFSInStack.size())
2216 return false;
2217
2218 Value *A, *B;
2219 CmpPredicate Pred;
2220 [[maybe_unused]] bool Matched =
2221 match(V: CmpToCheck, P: m_ICmpLike(Pred, L: m_Value(V&: A), R: m_Value(V&: B)));
2222 assert(Matched && "expected icmp-like match");
2223 // Check if the second condition can be simplified now.
2224 if (auto ImpliedCondition = checkCondition(Pred, A, B, CheckInst: CmpToCheck, Info)) {
2225 if (IsOr == *ImpliedCondition)
2226 JoinOp->replaceAllUsesWith(
2227 V: ConstantInt::getBool(Ty: JoinOp->getType(), V: *ImpliedCondition));
2228 else
2229 JoinOp->replaceAllUsesWith(V: JoinOp->getOperand(i: OtherOpIdx));
2230 ToRemove.push_back(Elt: JoinOp);
2231 return true;
2232 }
2233
2234 return false;
2235}
2236
2237void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B,
2238 unsigned NumIn, unsigned NumOut,
2239 SmallVectorImpl<StackEntry> &DFSInStack) {
2240 addFactImpl(Pred, A, B, NumIn, NumOut, DFSInStack, ForceSignedSystem: false);
2241 // If the Pred is eq/ne, also add the fact to signed system.
2242 if (CmpInst::isEquality(pred: Pred))
2243 addFactImpl(Pred, A, B, NumIn, NumOut, DFSInStack, ForceSignedSystem: true);
2244 if (Pred == CmpInst::ICMP_NE)
2245 tightenBoundUsingNe(A, B, NumIn, NumOut, DFSInStack);
2246}
2247
2248void ConstraintInfo::tightenBoundUsingNe(
2249 Value *A, Value *B, unsigned NumIn, unsigned NumOut,
2250 SmallVectorImpl<StackEntry> &DFSInStack) {
2251 if (!A->getType()->isIntOrPtrTy())
2252 return;
2253
2254 for (bool IsSigned : {false, true}) {
2255 // In the unsigned system `A u>= 0` holds for every A, so getConstraint
2256 // already turned `A != 0` into `A u> 0`.
2257 if (!IsSigned && match(V: B, P: m_Zero()))
2258 continue;
2259
2260 // Skip if there are any unknown variables.
2261 const auto &Value2Index = getValue2Index(Signed: IsSigned);
2262 if (any_of(Range: decompose(V: A, Info&: *this, IsSigned, DL).Vars,
2263 P: [&Value2Index](const DecompEntry &E) {
2264 return !Value2Index.contains(Val: E.Variable);
2265 }))
2266 continue;
2267
2268 // If the system implies `A >= B` then together with `A != B` we get the
2269 // strict `A > B`; symmetrically `A <= B` becomes `A < B`.
2270 CmpInst::Predicate GEPred =
2271 IsSigned ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
2272 CmpInst::Predicate LEPred =
2273 IsSigned ? CmpInst::ICMP_SLE : CmpInst::ICMP_ULE;
2274 for (CmpInst::Predicate NonStrict : {GEPred, LEPred}) {
2275 if (!doesHold(Pred: NonStrict, A, B))
2276 continue;
2277 CmpInst::Predicate Strict = CmpInst::getStrictPredicate(pred: NonStrict);
2278 LLVM_DEBUG(dbgs() << "Tightening '";
2279 dumpUnpackedICmp(dbgs(), NonStrict, A, B); dbgs() << "' to '";
2280 dumpUnpackedICmp(dbgs(), Strict, A, B);
2281 dbgs() << "' using inequality\n");
2282 addFactImpl(Pred: Strict, A, B, NumIn, NumOut, DFSInStack,
2283 /*ForceSignedSystem=*/false);
2284 break;
2285 }
2286 }
2287}
2288
2289void ConstraintInfo::addFactImpl(CmpInst::Predicate Pred, Value *A, Value *B,
2290 unsigned NumIn, unsigned NumOut,
2291 SmallVectorImpl<StackEntry> &DFSInStack,
2292 bool ForceSignedSystem) {
2293 SmallVector<Value *> NewVariables;
2294 auto R = getConstraint(Pred, Op0: A, Op1: B, NewVariables, ForceSignedSystem);
2295
2296 // TODO: Support non-equality for facts as well.
2297 if (R.empty() || R.isNe())
2298 return;
2299
2300 auto &CSToUse = getCS(Signed: R.IsSigned);
2301 // A row implied by a single existing row adds no information. Rows in the
2302 // system are removed in reverse order, so the existing row outlives R. Rows
2303 // in the system are normalized, so normalize R before comparing.
2304 if (!R.isEq() && NewVariables.empty()) {
2305 ConstraintSystem::normalizeByGCD(R: R.Coefficients);
2306 if (CSToUse.isImpliedBySingleRow(R: R.Coefficients))
2307 return;
2308 }
2309 LLVM_DEBUG(dbgs() << "Adding '"; dumpUnpackedICmp(dbgs(), Pred, A, B);
2310 dbgs() << "'\n");
2311 bool Added = CSToUse.addRow(R: R.Coefficients, NumVars: R.NumVars);
2312 if (!Added)
2313 return;
2314
2315 DecomposeCache.clear();
2316
2317 // If R has been added to the system, add the new variables and queue it for
2318 // removal once it goes out-of-scope.
2319 SmallVector<Value *, 2> ValuesToRelease;
2320 auto &Value2Index = getValue2Index(Signed: R.IsSigned);
2321 for (Value *V : NewVariables) {
2322 Value2Index.try_emplace(Key: V, Args: Value2Index.size() + 1);
2323 ValuesToRelease.push_back(Elt: V);
2324 }
2325
2326 LLVM_DEBUG({
2327 dbgs() << " constraint: ";
2328 dumpConstraint(R.Coefficients, getValue2Index(R.IsSigned));
2329 dbgs() << "\n";
2330 });
2331
2332 DFSInStack.emplace_back(Args&: NumIn, Args&: NumOut, Args&: R.IsSigned,
2333 Args: std::move(ValuesToRelease));
2334
2335 if (!R.IsSigned) {
2336 for (Value *V : NewVariables) {
2337 // Add V > -1 constraints for all new variables.
2338 CSToUse.addRow(R: {Entry(0, 0), Entry(-1, Value2Index.at(Val: V))},
2339 NumVars: Value2Index.size());
2340 DFSInStack.emplace_back(Args&: NumIn, Args&: NumOut, Args&: R.IsSigned,
2341 Args: SmallVector<Value *, 2>());
2342 }
2343 }
2344
2345 if (R.isEq()) {
2346 // Also add the inverted constraint for equality constraints.
2347 for (Entry &E : R.Coefficients)
2348 if (MulOverflow(X: E.Coefficient, Y: int64_t(-1), Result&: E.Coefficient))
2349 return;
2350 CSToUse.addRow(R: R.Coefficients, NumVars: R.NumVars);
2351
2352 DFSInStack.emplace_back(Args&: NumIn, Args&: NumOut, Args&: R.IsSigned,
2353 Args: SmallVector<Value *, 2>());
2354 }
2355}
2356
2357/// Replace the uses of \p II, which is known not to overflow, by the
2358/// corresponding plain binary operation and a false overflow flag.
2359static bool replaceOverflowUses(WithOverflowInst *II,
2360 SmallVectorImpl<Instruction *> &ToRemove) {
2361 bool Changed = false;
2362 IRBuilder<> Builder(II->getIterator());
2363 Value *Res = nullptr;
2364 for (User *U : make_early_inc_range(Range: II->users())) {
2365 if (match(V: U, P: m_ExtractValue<0>(V: m_Value()))) {
2366 if (!Res)
2367 Res = Builder.CreateNoWrapBinOp(Opc: II->getBinaryOp(), LHS: II->getLHS(),
2368 RHS: II->getRHS(),
2369 /*IsNUW=*/!II->isSigned(),
2370 /*IsNSW=*/II->isSigned());
2371 U->replaceAllUsesWith(V: Res);
2372 Changed = true;
2373 } else if (match(V: U, P: m_ExtractValue<1>(V: m_Value()))) {
2374 U->replaceAllUsesWith(V: Builder.getFalse());
2375 Changed = true;
2376 } else
2377 continue;
2378
2379 if (U->use_empty()) {
2380 auto *I = cast<Instruction>(Val: U);
2381 ToRemove.push_back(Elt: I);
2382 I->setOperand(i: 0, Val: PoisonValue::get(T: II->getType()));
2383 Changed = true;
2384 }
2385 }
2386
2387 if (II->use_empty()) {
2388 // Do not erase II here: the worklist may still hold Uses of II's operands.
2389 for (Use &Arg : II->args())
2390 Arg.set(PoisonValue::get(T: Arg->getType()));
2391 ToRemove.push_back(Elt: II);
2392 Changed = true;
2393 }
2394 return Changed;
2395}
2396
2397static bool
2398tryToSimplifyOverflowMath(WithOverflowInst *II, ConstraintInfo &Info,
2399 SmallVectorImpl<Instruction *> &ToRemove) {
2400 if (!isKnownNoWrap(V: II, Info, Signed: II->isSigned()))
2401 return false;
2402 return replaceOverflowUses(II, ToRemove);
2403}
2404
2405static bool eliminateConstraints(Function &F, DominatorTree &DT, LoopInfo &LI,
2406 ScalarEvolution *SE,
2407 OptimizationRemarkEmitter &ORE,
2408 TargetLibraryInfo &TLI) {
2409 const ScalarOptions &Opts =
2410 F.getContext().getLibraryOptions().get<ScalarOptions>();
2411 bool Changed = false;
2412 DT.updateDFSNumbers();
2413 SmallVector<Value *> FunctionArgs(llvm::make_pointer_range(Range: F.args()));
2414 ConstraintInfo Info(F.getDataLayout(), FunctionArgs);
2415 State S(DT, LI, SE, TLI);
2416 std::unique_ptr<Module> ReproducerModule(
2417 Opts.constraint_elimination_dump_reproducers
2418 ? new Module(F.getName(), F.getContext())
2419 : nullptr);
2420
2421 // First, collect conditions implied by branches and blocks with their
2422 // Dominator DFS in and out numbers.
2423 for (BasicBlock &BB : F) {
2424 if (!DT.getNode(BB: &BB))
2425 continue;
2426 S.addInfoFor(BB);
2427 }
2428
2429 // Next, sort worklist by dominance, so that dominating conditions to check
2430 // and facts come before conditions and facts dominated by them. If a
2431 // condition to check and a fact have the same numbers, conditional facts come
2432 // first. Assume facts and checks are ordered according to their relative
2433 // order in the containing basic block. Also make sure conditions with
2434 // constant operands come before conditions without constant operands. This
2435 // increases the effectiveness of the current signed <-> unsigned fact
2436 // transfer logic.
2437 stable_sort(Range&: S.WorkList, C: [](const FactOrCheck &A, const FactOrCheck &B) {
2438 auto HasNoConstOp = [](const FactOrCheck &B) {
2439 Value *V0 = B.isConditionFact() ? B.Cond.Op0 : B.Inst->getOperand(i: 0);
2440 Value *V1 = B.isConditionFact() ? B.Cond.Op1 : B.Inst->getOperand(i: 1);
2441 return !isa<ConstantInt>(Val: V0) && !isa<ConstantInt>(Val: V1);
2442 };
2443 // If both entries have the same In numbers, conditional facts come first.
2444 // Otherwise use the relative order in the basic block.
2445 if (A.NumIn == B.NumIn) {
2446 if (A.isConditionFact() && B.isConditionFact()) {
2447 bool NoConstOpA = HasNoConstOp(A);
2448 bool NoConstOpB = HasNoConstOp(B);
2449 return NoConstOpA < NoConstOpB;
2450 }
2451 if (A.isConditionFact())
2452 return true;
2453 if (B.isConditionFact())
2454 return false;
2455 auto *InstA = A.getContextInst();
2456 auto *InstB = B.getContextInst();
2457 return InstA->comesBefore(Other: InstB);
2458 }
2459 return A.NumIn < B.NumIn;
2460 });
2461
2462 SmallVector<Instruction *> ToRemove;
2463
2464 // Finally, process ordered worklist and eliminate implied conditions.
2465 SmallVector<StackEntry, 16> DFSInStack;
2466 SmallVector<ReproducerEntry> ReproducerCondStack;
2467 for (FactOrCheck &CB : S.WorkList) {
2468 // First, pop entries from the stack that are out-of-scope for CB. Remove
2469 // the corresponding entry from the constraint system.
2470 while (!DFSInStack.empty()) {
2471 auto &E = DFSInStack.back();
2472 LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
2473 << "\n");
2474 LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
2475 assert(E.NumIn <= CB.NumIn);
2476 if (CB.NumOut <= E.NumOut)
2477 break;
2478 LLVM_DEBUG({
2479 dbgs() << "Removing ";
2480 dumpConstraint(Info.getCS(E.IsSigned).getLastConstraint(),
2481 Info.getValue2Index(E.IsSigned));
2482 dbgs() << "\n";
2483 });
2484 removeEntryFromStack(E, Info, ReproducerModule: ReproducerModule.get(), ReproducerCondStack,
2485 DFSInStack);
2486 }
2487
2488 CmpPredicate Pred;
2489 Value *A, *B;
2490 // For a block, check if any CmpInsts become known based on the current set
2491 // of constraints.
2492 if (CB.isCheck()) {
2493 Instruction *Inst = CB.getInstructionToSimplify();
2494 if (!Inst)
2495 continue;
2496 if (canStrengthenFlags(I: Inst)) {
2497 Changed |= tryToStrengthenFlags(I: Inst, Info);
2498 continue;
2499 }
2500 LLVM_DEBUG(dbgs() << "Processing condition to simplify: " << *Inst
2501 << "\n");
2502 if (auto *II = dyn_cast<WithOverflowInst>(Val: Inst)) {
2503 Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove);
2504 } else if (match(V: Inst, P: m_ICmpLike(Pred, L: m_Value(V&: A), R: m_Value(V&: B)))) {
2505 bool Simplified = checkAndReplaceCondition(
2506 Pred, A, B, CheckInst: Inst, Info, NumIn: CB.NumIn, NumOut: CB.NumOut, ContextInst: CB.getContextInst(),
2507 ReproducerModule: ReproducerModule.get(), ReproducerCondStack, DT&: S.DT, ToRemove);
2508 if (!Simplified &&
2509 match(V: CB.getContextInst(), P: m_LogicalOp(L: m_Value(), R: m_Value()))) {
2510 Simplified = checkOrAndOpImpliedByOther(
2511 CB, Info, ReproducerModule: ReproducerModule.get(), ReproducerCondStack, DFSInStack,
2512 ToRemove);
2513 }
2514 Changed |= Simplified;
2515 } else if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(Val: Inst)) {
2516 Changed |= checkAndReplaceMinMax(MinMax, Info, ToRemove);
2517 } else if (auto *CmpIntr = dyn_cast<CmpIntrinsic>(Val: Inst)) {
2518 Changed |= checkAndReplaceCmp(I: CmpIntr, Info, ToRemove);
2519 } else if (match(V: Inst, P: m_Intrinsic<Intrinsic::usub_sat>())) {
2520 Changed |=
2521 checkAndReplaceUSubSat(USub: cast<SaturatingInst>(Val: Inst), Info, ToRemove);
2522 }
2523 continue;
2524 }
2525
2526 auto AddFact = [&](CmpPredicate Pred, Value *A, Value *B) {
2527 LLVM_DEBUG(dbgs() << "Processing fact to add to the system: ";
2528 dumpUnpackedICmp(dbgs(), Pred, A, B); dbgs() << "\n");
2529 if (Info.getCS(Signed: CmpInst::isSigned(Pred)).size() >
2530 Opts.constraint_elimination_max_rows) {
2531 LLVM_DEBUG(
2532 dbgs()
2533 << "Skip adding constraint because system has too many rows.\n");
2534 return;
2535 }
2536
2537 Info.addFact(Pred, A, B, NumIn: CB.NumIn, NumOut: CB.NumOut, DFSInStack);
2538 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size())
2539 ReproducerCondStack.emplace_back(Args&: Pred, Args&: A, Args&: B);
2540
2541 if (ICmpInst::isRelational(P: Pred)) {
2542 // If samesign is present on the ICmp, simply flip the sign of the
2543 // predicate, transferring the information from the signed system to the
2544 // unsigned system, and viceversa.
2545 if (Pred.hasSameSign())
2546 Info.addFact(Pred: ICmpInst::getFlippedSignednessPredicate(Pred), A, B,
2547 NumIn: CB.NumIn, NumOut: CB.NumOut, DFSInStack);
2548 else
2549 Info.transferToOtherSystem(Pred, A, B, NumIn: CB.NumIn, NumOut: CB.NumOut,
2550 DFSInStack);
2551 }
2552
2553 // (X | Y) >s -1 implies X >s -1 and Y >s -1, because the sign bit of an
2554 // OR is the OR of the operand sign bits. Similarly, (X & Y) <s 0 implies
2555 // X <s 0 and Y <s 0. Look through these canonical forms produced by
2556 // InstCombine so the sign facts on the operands are available to the
2557 // solver.
2558 if ((Pred == CmpInst::ICMP_SGT && match(V: B, P: m_AllOnes())) ||
2559 (Pred == CmpInst::ICMP_SLT && match(V: B, P: m_Zero()))) {
2560 unsigned Opc =
2561 Pred == CmpInst::ICMP_SGT ? Instruction::Or : Instruction::And;
2562 SmallVector<Value *> Worklist = {A};
2563 SmallPtrSet<Value *, 4> Seen;
2564 while (!Worklist.empty()) {
2565 Value *Cur = Worklist.pop_back_val();
2566 auto *BO = dyn_cast<BinaryOperator>(Val: Cur);
2567 if (!BO || BO->getOpcode() != Opc)
2568 continue;
2569 for (Value *Op : {BO->getOperand(i_nocapture: 0), BO->getOperand(i_nocapture: 1)}) {
2570 if (!Seen.insert(Ptr: Op).second)
2571 continue;
2572 Worklist.push_back(Elt: Op);
2573 Info.addFact(Pred, A: Op, B, NumIn: CB.NumIn, NumOut: CB.NumOut, DFSInStack);
2574 }
2575 }
2576 }
2577
2578 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size()) {
2579 // Add dummy entries to ReproducerCondStack to keep it in sync with
2580 // DFSInStack.
2581 for (unsigned I = 0,
2582 E = (DFSInStack.size() - ReproducerCondStack.size());
2583 I < E; ++I) {
2584 ReproducerCondStack.emplace_back(Args: ICmpInst::BAD_ICMP_PREDICATE,
2585 Args: nullptr, Args: nullptr);
2586 }
2587 }
2588 };
2589
2590 if (!CB.isConditionFact()) {
2591 Value *X;
2592 if (match(V: CB.Inst, P: m_Intrinsic<Intrinsic::abs>(Ops: m_Value(V&: X)))) {
2593 // If is_int_min_poison is true then we may assume llvm.abs >= 0.
2594 if (cast<ConstantInt>(Val: CB.Inst->getOperand(i: 1))->isOne())
2595 AddFact(CmpInst::ICMP_SGE, CB.Inst,
2596 ConstantInt::get(Ty: CB.Inst->getType(), V: 0));
2597 AddFact(CmpInst::ICMP_SGE, CB.Inst, X);
2598 continue;
2599 }
2600
2601 if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(Val: CB.Inst)) {
2602 Pred = ICmpInst::getNonStrictPredicate(pred: MinMax->getPredicate());
2603 AddFact(Pred, MinMax, MinMax->getLHS());
2604 AddFact(Pred, MinMax, MinMax->getRHS());
2605 continue;
2606 }
2607 if (auto *USatI = dyn_cast<SaturatingInst>(Val: CB.Inst)) {
2608 switch (USatI->getIntrinsicID()) {
2609 default:
2610 llvm_unreachable("Unexpected intrinsic.");
2611 case Intrinsic::uadd_sat:
2612 AddFact(ICmpInst::ICMP_UGE, USatI, USatI->getLHS());
2613 AddFact(ICmpInst::ICMP_UGE, USatI, USatI->getRHS());
2614 break;
2615 case Intrinsic::usub_sat:
2616 AddFact(ICmpInst::ICMP_ULE, USatI, USatI->getLHS());
2617 break;
2618 }
2619 continue;
2620 }
2621
2622 if (auto *BO = dyn_cast<BinaryOperator>(Val: CB.Inst)) {
2623 if (BO->getOpcode() == Instruction::URem) {
2624 // urem x, n: result < n (remainder is always less than divisor)
2625 AddFact(CmpInst::ICMP_ULT, BO, BO->getOperand(i_nocapture: 1));
2626 // urem x, n: result <= x (remainder is at most the dividend)
2627 AddFact(CmpInst::ICMP_ULE, BO, BO->getOperand(i_nocapture: 0));
2628 continue;
2629 }
2630 if (BO->getOpcode() == Instruction::UDiv) {
2631 // udiv x, n: result <= x (quotient is at most the dividend)
2632 AddFact(CmpInst::ICMP_ULE, BO, BO->getOperand(i_nocapture: 0));
2633 continue;
2634 }
2635 if (BO->getOpcode() == Instruction::LShr) {
2636 // lshr x, n: result <= x (right shift cannot increase the value)
2637 AddFact(CmpInst::ICMP_ULE, BO, BO->getOperand(i_nocapture: 0));
2638 continue;
2639 }
2640 if (BO->getOpcode() == Instruction::SRem) {
2641 Value *X = BO->getOperand(i_nocapture: 0);
2642 Value *N = BO->getOperand(i_nocapture: 1);
2643 Constant *Zero = Constant::getNullValue(Ty: BO->getType());
2644 if (Info.doesHold(Pred: CmpInst::ICMP_SGE, A: X, B: Zero) ||
2645 isKnownNonNegative(V: X, SQ: F.getDataLayout())) {
2646 // srem x, n: result >= 0, if x >= 0 (result has the sign of x)
2647 AddFact(CmpInst::ICMP_SGE, BO, Zero);
2648 // srem x, n: result <= x, if x >= 0 (|result| <= |x| and both are
2649 // non-negative)
2650 AddFact(CmpInst::ICMP_SLE, BO, X);
2651 }
2652 if (Info.doesHold(Pred: CmpInst::ICMP_SGE, A: N, B: Zero) ||
2653 isKnownPositive(V: N, SQ: F.getDataLayout())) {
2654 // srem x, n: result <= n, if n >= 0 (|result| < n, so result <= n -
2655 // 1
2656 AddFact(CmpInst::ICMP_SLT, BO, N);
2657 }
2658 continue;
2659 }
2660 if (BO->getOpcode() == Instruction::SDiv) {
2661 Value *X = BO->getOperand(i_nocapture: 0);
2662 Value *N = BO->getOperand(i_nocapture: 1);
2663 if (!Info.isKnownNonNegative(V: X) || !Info.isKnownPositive(V: N))
2664 continue;
2665
2666 bool IsStrict = Info.isKnownPositive(V: X) &&
2667 Info.doesHold(Pred: CmpInst::ICMP_SGT, A: N,
2668 B: ConstantInt::get(Ty: N->getType(), V: 1));
2669 AddFact(CmpInst::ICMP_SGE, BO, Constant::getNullValue(Ty: BO->getType()));
2670 AddFact(IsStrict ? CmpInst::ICMP_SLT : CmpInst::ICMP_SLE, BO, X);
2671 continue;
2672 }
2673 }
2674
2675 auto &DL = F.getDataLayout();
2676 auto AddFactsAboutIndices = [&](Value *Ptr, Type *AccessType) {
2677 CmpPredicate Pred;
2678 Value *A, *B;
2679 if (getConstraintFromMemoryAccess(
2680 GEP&: *cast<GetElementPtrInst>(Val: Ptr),
2681 AccessSize: DL.getTypeStoreSize(Ty: AccessType).getFixedValue(), Pred, A, B, DL,
2682 TLI))
2683 AddFact(Pred, A, B);
2684 };
2685
2686 if (auto *LI = dyn_cast<LoadInst>(Val: CB.Inst)) {
2687 AddFactsAboutIndices(LI->getPointerOperand(), LI->getAccessType());
2688 continue;
2689 }
2690 if (auto *SI = dyn_cast<StoreInst>(Val: CB.Inst)) {
2691 AddFactsAboutIndices(SI->getPointerOperand(), SI->getAccessType());
2692 continue;
2693 }
2694 }
2695
2696 if (CB.isConditionFact()) {
2697 Pred = CB.Cond.Pred;
2698 A = CB.Cond.Op0;
2699 B = CB.Cond.Op1;
2700 if (CB.DoesHold.Pred != CmpInst::BAD_ICMP_PREDICATE &&
2701 !Info.doesHold(Pred: CB.DoesHold.Pred, A: CB.DoesHold.Op0, B: CB.DoesHold.Op1)) {
2702 LLVM_DEBUG({
2703 dbgs() << "Not adding fact ";
2704 dumpUnpackedICmp(dbgs(), Pred, A, B);
2705 dbgs() << " because precondition ";
2706 dumpUnpackedICmp(dbgs(), CB.DoesHold.Pred, CB.DoesHold.Op0,
2707 CB.DoesHold.Op1);
2708 dbgs() << " does not hold.\n";
2709 });
2710 continue;
2711 }
2712 } else {
2713 [[maybe_unused]] bool Matched =
2714 match(V: CB.Inst, P: m_Intrinsic<Intrinsic::assume>(
2715 Ops: m_ICmpLike(Pred, L: m_Value(V&: A), R: m_Value(V&: B))));
2716 assert(Matched &&
2717 "Must have an assume intrinsic with a icmp like operand");
2718 }
2719 AddFact(Pred, A, B);
2720 }
2721
2722 if (ReproducerModule && !ReproducerModule->functions().empty()) {
2723 std::string S;
2724 raw_string_ostream StringS(S);
2725 ReproducerModule->print(OS&: StringS, AAW: nullptr);
2726 OptimizationRemark Rem(DEBUG_TYPE, "Reproducer", &F);
2727 Rem << ore::NV("module") << S;
2728 ORE.emit(OptDiag&: Rem);
2729 }
2730
2731#ifndef NDEBUG
2732 unsigned SignedEntries =
2733 count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; });
2734 assert(Info.getCS(false).size() - FunctionArgs.size() ==
2735 DFSInStack.size() - SignedEntries &&
2736 "updates to CS and DFSInStack are out of sync");
2737 assert(Info.getCS(true).size() == SignedEntries &&
2738 "updates to CS and DFSInStack are out of sync");
2739#endif
2740
2741 for (Instruction *I : ToRemove)
2742 I->eraseFromParent();
2743 return Changed;
2744}
2745
2746PreservedAnalyses ConstraintEliminationPass::run(Function &F,
2747 FunctionAnalysisManager &AM) {
2748 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
2749 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
2750 // SCEV is only used for loops, only construct it if there are some.
2751 auto *SE = LI.empty() ? nullptr : &AM.getResult<ScalarEvolutionAnalysis>(IR&: F);
2752 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
2753 auto &TLI = AM.getResult<TargetLibraryAnalysis>(IR&: F);
2754 if (!eliminateConstraints(F, DT, LI, SE, ORE, TLI))
2755 return PreservedAnalyses::all();
2756
2757 PreservedAnalyses PA;
2758 PA.preserve<ScalarEvolutionAnalysis>();
2759 PA.preserveSet<CFGAnalyses>();
2760 return PA;
2761}
2762