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