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