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