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