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