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

source code of llvm/lib/Transforms/Scalar/ConstraintElimination.cpp