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