LLVM 19.0.0git
ConstraintElimination.cpp
Go to the documentation of this file.
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
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/ScopeExit.h"
18#include "llvm/ADT/Statistic.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"
33#include "llvm/IR/Verifier.h"
34#include "llvm/Pass.h"
36#include "llvm/Support/Debug.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
56 MaxRows("constraint-elimination-max-rows", cl::init(500), cl::Hidden,
57 cl::desc("Maximum number of rows to keep in constraint system"));
58
60 "constraint-elimination-dump-reproducers", cl::init(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(A, 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(A, B, Result);
77 return Result;
78}
79
81 Instruction *UserI = cast<Instruction>(U.getUser());
82 if (auto *Phi = dyn_cast<PHINode>(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 {
91 Value *Op0;
92 Value *Op1;
93
95 : Pred(CmpInst::BAD_ICMP_PREDICATE), Op0(nullptr), Op1(nullptr) {}
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;
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);
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>(*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;
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(BasicBlockEdge(&BB, Succ), 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
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(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(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;
352
353 Decomposition(int64_t Offset) : Offset(Offset) {}
354 Decomposition(Value *V, bool IsKnownNonNegative = false) {
355 Vars.emplace_back(1, V, 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(Offset, OtherOffset);
362 }
363
364 void add(const Decomposition &Other) {
365 add(Other.Offset);
366 append_range(Vars, Other.Vars);
367 }
368
369 void sub(const Decomposition &Other) {
370 Decomposition Tmp = Other;
371 Tmp.mul(-1);
372 add(Tmp.Offset);
373 append_range(Vars, Tmp.Vars);
374 }
375
376 void mul(int64_t Factor) {
377 Offset = multiplyWithOverflow(Offset, Factor);
378 for (auto &Var : Vars)
379 Var.Coefficient = multiplyWithOverflow(Var.Coefficient, 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(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, Result.VariableOffsets,
406 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>(Result.BasePtr)) {
412 MapVector<Value *, APInt> VariableOffsets2;
413 APInt ConstantOffset2(BitWidth, 0);
414 bool CanCollectInner = InnerGEP->collectOffset(
415 DL, BitWidth, VariableOffsets2, 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();
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(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] =
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(Index, Preconditions, IsSigned, DL);
459 IdxResult.mul(Scale.getSExtValue());
460 Result.add(IdxResult);
461
462 // If Op0 is signed non-negative, the GEP is increasing monotonically and
463 // can be de-composed.
465 Preconditions.emplace_back(CmpInst::ICMP_SGE, Index,
466 ConstantInt::get(Index->getType(), 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(A, Preconditions, IsSigned, DL);
481 auto ResB = decompose(B, Preconditions, IsSignedB, DL);
482 ResA.add(ResB);
483 return ResA;
484 };
485
486 Type *Ty = V->getType()->getScalarType();
487 if (Ty->isPointerTy() && !IsSigned) {
488 if (auto *GEP = dyn_cast<GEPOperator>(V))
489 return decomposeGEP(*GEP, Preconditions, IsSigned, DL);
490 if (isa<ConstantPointerNull>(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>(V)) {
507 if (canUseSExt(CI))
508 return CI->getSExtValue();
509 }
510 Value *Op0;
511 Value *Op1;
512
513 if (match(V, m_SExt(m_Value(Op0))))
514 V = Op0;
515 else if (match(V, m_NNegZExt(m_Value(Op0)))) {
516 V = Op0;
517 IsKnownNonNegative = true;
518 }
519
520 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1))))
521 return MergeResults(Op0, Op1, IsSigned);
522
523 ConstantInt *CI;
524 if (match(V, m_NSWMul(m_Value(Op0), m_ConstantInt(CI))) && canUseSExt(CI)) {
525 auto Result = decompose(Op0, Preconditions, IsSigned, DL);
526 Result.mul(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, m_NSWShl(m_Value(Op0), 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(Op0, Preconditions, IsSigned, DL);
537 Result.mul(int64_t(1) << Shift);
538 return Result;
539 }
540 }
541
542 return {V, IsKnownNonNegative};
543 }
544
545 if (auto *CI = dyn_cast<ConstantInt>(V)) {
546 if (CI->uge(MaxConstraintValue))
547 return V;
548 return int64_t(CI->getZExtValue());
549 }
550
551 Value *Op0;
552 if (match(V, m_ZExt(m_Value(Op0)))) {
553 IsKnownNonNegative = true;
554 V = Op0;
555 }
556
557 Value *Op1;
558 ConstantInt *CI;
559 if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) {
560 return MergeResults(Op0, Op1, IsSigned);
561 }
562 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) {
563 if (!isKnownNonNegative(Op0, DL))
564 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,
565 ConstantInt::get(Op0->getType(), 0));
566 if (!isKnownNonNegative(Op1, DL))
567 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op1,
568 ConstantInt::get(Op1->getType(), 0));
569
570 return MergeResults(Op0, Op1, IsSigned);
571 }
572
573 if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() &&
574 canUseSExt(CI)) {
575 Preconditions.emplace_back(
577 ConstantInt::get(Op0->getType(), 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, m_DisjointOr(m_Value(Op0), m_ConstantInt(CI))))
583 return MergeResults(Op0, CI, IsSigned);
584
585 if (match(V, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI)) {
586 if (CI->getSExtValue() < 0 || CI->getSExtValue() >= 64)
587 return {V, IsKnownNonNegative};
588 auto Result = decompose(Op1, Preconditions, IsSigned, DL);
589 Result.mul(int64_t{1} << CI->getSExtValue());
590 return Result;
591 }
592
593 if (match(V, m_NUWMul(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI) &&
594 (!CI->isNegative())) {
595 auto Result = decompose(Op1, Preconditions, IsSigned, DL);
596 Result.mul(CI->getSExtValue());
597 return Result;
598 }
599
600 if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1)))) {
601 auto ResA = decompose(Op0, Preconditions, IsSigned, DL);
602 auto ResB = decompose(Op1, Preconditions, IsSigned, DL);
603 ResA.sub(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) {
622 case CmpInst::ICMP_SGE: {
623 Pred = CmpInst::getSwappedPredicate(Pred);
624 std::swap(Op0, Op1);
625 break;
626 }
627 case CmpInst::ICMP_EQ:
628 if (match(Op1, 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(Op1, m_Zero())) {
638 std::swap(Op0, 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(Pred);
654 auto &Value2Index = getValue2Index(IsSigned);
656 Preconditions, IsSigned, DL);
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.
669 auto GetOrAddIndex = [&Value2Index, &NewVariables,
670 &NewIndexMap](Value *V) -> unsigned {
671 auto V2I = Value2Index.find(V);
672 if (V2I != Value2Index.end())
673 return V2I->second;
674 auto Insert =
675 NewIndexMap.insert({V, Value2Index.size() + NewVariables.size() + 1});
676 if (Insert.second)
677 NewVariables.push_back(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>(VariablesA, 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.Variable, KV.IsKnownNonNegative});
698 I.first->second &= KV.IsKnownNonNegative;
699 }
700
701 for (const auto &KV : VariablesB) {
702 if (SubOverflow(R[GetOrAddIndex(KV.Variable)], KV.Coefficient,
703 R[GetOrAddIndex(KV.Variable)]))
704 return {};
705 auto I =
706 KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative});
707 I.first->second &= KV.IsKnownNonNegative;
708 }
709
710 int64_t OffsetSum;
711 if (AddOverflow(Offset1, Offset2, OffsetSum))
712 return {};
713 if (Pred == (IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT))
714 if (AddOverflow(OffsetSum, int64_t(-1), 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(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(KV.first) && !NewIndexMap.contains(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(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(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(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(Pred) &&
760 isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1) &&
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(Preconditions, [&Info](const ConditionTy &C) {
774 return Info.doesHold(C.Pred, C.Op0, C.Op1);
775 });
776}
777
778std::optional<bool>
779ConstraintTy::isImpliedBy(const ConstraintSystem &CS) const {
780 bool IsConditionImplied = CS.isConditionImplied(Coefficients);
781
782 if (IsEq || IsNe) {
783 auto NegatedOrEqual = ConstraintSystem::negateOrEqual(Coefficients);
784 bool IsNegatedOrEqualImplied =
785 !NegatedOrEqual.empty() && CS.isConditionImplied(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(Coefficients);
794 bool IsNegatedImplied = !Negated.empty() && CS.isConditionImplied(Negated);
795
796 auto StrictLessThan = ConstraintSystem::toStrictLessThan(Coefficients);
797 bool IsStrictLessThanImplied =
798 !StrictLessThan.empty() && CS.isConditionImplied(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(Coefficients);
814 auto IsNegatedImplied = !Negated.empty() && CS.isConditionImplied(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, A, B);
825 return R.isValid(*this) &&
826 getCS(R.IsSigned).isConditionImplied(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(CmpInst::ICMP_SGE, V, ConstantInt::get(V->getType(), 0)) ||
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;
848 // If B is a signed positive constant, then A >=s 0 and A <s (or <=s) B.
849 if (IsKnownNonNegative(B)) {
850 addFact(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0), NumIn,
851 NumOut, DFSInStack);
852 addFact(CmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut,
853 DFSInStack);
854 }
855 break;
858 // If A is a signed positive constant, then B >=s 0 and A >s (or >=s) B.
859 if (IsKnownNonNegative(A)) {
860 addFact(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0), NumIn,
861 NumOut, DFSInStack);
862 addFact(CmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut,
863 DFSInStack);
864 }
865 break;
867 if (IsKnownNonNegative(A))
868 addFact(CmpInst::ICMP_ULT, A, B, NumIn, NumOut, DFSInStack);
869 break;
870 case CmpInst::ICMP_SGT: {
871 if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), -1)))
872 addFact(CmpInst::ICMP_UGE, A, ConstantInt::get(B->getType(), 0), NumIn,
873 NumOut, DFSInStack);
874 if (IsKnownNonNegative(B))
875 addFact(CmpInst::ICMP_UGT, A, B, NumIn, NumOut, DFSInStack);
876
877 break;
878 }
880 if (IsKnownNonNegative(B))
881 addFact(CmpInst::ICMP_UGE, A, B, NumIn, NumOut, DFSInStack);
882 break;
883 }
884}
885
886#ifndef NDEBUG
887
889 const DenseMap<Value *, unsigned> &Value2Index) {
890 ConstraintSystem CS(Value2Index);
892 CS.dump();
893}
894#endif
895
896void State::addInfoForInductions(BasicBlock &BB) {
897 auto *L = LI.getLoopFor(&BB);
898 if (!L || L->getHeader() != &BB)
899 return;
900
901 Value *A;
902 Value *B;
904
905 if (!match(BB.getTerminator(),
906 m_Br(m_ICmp(Pred, m_Value(A), m_Value(B)), m_Value(), m_Value())))
907 return;
908 PHINode *PN = dyn_cast<PHINode>(A);
909 if (!PN) {
910 Pred = CmpInst::getSwappedPredicate(Pred);
911 std::swap(A, B);
912 PN = dyn_cast<PHINode>(A);
913 }
914
915 if (!PN || PN->getParent() != &BB || PN->getNumIncomingValues() != 2 ||
916 !SE.isSCEVable(PN->getType()))
917 return;
918
919 BasicBlock *InLoopSucc = nullptr;
920 if (Pred == CmpInst::ICMP_NE)
921 InLoopSucc = cast<BranchInst>(BB.getTerminator())->getSuccessor(0);
922 else if (Pred == CmpInst::ICMP_EQ)
923 InLoopSucc = cast<BranchInst>(BB.getTerminator())->getSuccessor(1);
924 else
925 return;
926
927 if (!L->contains(InLoopSucc) || !L->isLoopExiting(&BB) || InLoopSucc == &BB)
928 return;
929
930 auto *AR = dyn_cast_or_null<SCEVAddRecExpr>(SE.getSCEV(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>(StartSCEV)) {
938 StartValue = C->getValue();
939 } else {
940 StartValue = PN->getIncomingValueForBlock(LoopPred);
941 assert(SE.getSCEV(StartValue) == StartSCEV && "inconsistent start value");
942 }
943
944 DomTreeNode *DTN = DT.getNode(InLoopSucc);
945 auto IncUnsigned = SE.getMonotonicPredicateType(AR, CmpInst::ICMP_UGT);
946 auto IncSigned = SE.getMonotonicPredicateType(AR, 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 FactOrCheck::getConditionFact(DTN, CmpInst::ICMP_UGE, PN, StartValue));
956 if (MonotonicallyIncreasingSigned)
957 WorkList.push_back(
958 FactOrCheck::getConditionFact(DTN, CmpInst::ICMP_SGE, PN, StartValue));
959
960 APInt StepOffset;
961 if (auto *C = dyn_cast<SCEVConstant>(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(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(FactOrCheck::getConditionFact(
980 DTN, CmpInst::ICMP_UGE, StartValue, PN,
981 ConditionTy(CmpInst::ICMP_ULE, B, StartValue)));
982 WorkList.push_back(FactOrCheck::getConditionFact(
983 DTN, CmpInst::ICMP_SGE, StartValue, PN,
984 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(FactOrCheck::getConditionFact(
988 DTN, CmpInst::ICMP_UGT, PN, B,
989 ConditionTy(CmpInst::ICMP_ULE, B, StartValue)));
990 WorkList.push_back(FactOrCheck::getConditionFact(
991 DTN, CmpInst::ICMP_SGT, PN, B,
992 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(SE.getSCEV(B), StartSCEV);
1005 if (isa<SCEVCouldNotCompute>(BMinusStart) ||
1006 !SE.getConstantMultiple(BMinusStart).urem(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(FactOrCheck::getConditionFact(
1015 DTN, CmpInst::ICMP_UGE, PN, StartValue,
1016 ConditionTy(CmpInst::ICMP_ULE, StartValue, B)));
1017 if (!MonotonicallyIncreasingSigned)
1018 WorkList.push_back(FactOrCheck::getConditionFact(
1019 DTN, CmpInst::ICMP_SGE, PN, StartValue,
1020 ConditionTy(CmpInst::ICMP_SLE, StartValue, B)));
1021
1022 WorkList.push_back(FactOrCheck::getConditionFact(
1023 DTN, CmpInst::ICMP_ULT, PN, B,
1024 ConditionTy(CmpInst::ICMP_ULE, StartValue, B)));
1025 WorkList.push_back(FactOrCheck::getConditionFact(
1026 DTN, CmpInst::ICMP_SLT, PN, B,
1027 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>(&I)) {
1038 for (Use &U : Cmp->uses()) {
1039 auto *UserI = getContextInstForUse(U);
1040 auto *DTN = DT.getNode(UserI->getParent());
1041 if (!DTN)
1042 continue;
1043 WorkList.push_back(FactOrCheck::getCheck(DTN, &U));
1044 }
1045 continue;
1046 }
1047
1048 auto *II = dyn_cast<IntrinsicInst>(&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(I.getOperand(0), m_ICmp(Pred, m_Value(A), m_Value(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(FactOrCheck::getConditionFact(
1060 DT.getNode(I.getParent()), Pred, A, B));
1061 } else {
1062 WorkList.emplace_back(
1063 FactOrCheck::getInstFact(DT.getNode(I.getParent()), &I));
1064 }
1065 break;
1066 }
1067 // Enqueue ssub_with_overflow for simplification.
1068 case Intrinsic::ssub_with_overflow:
1069 WorkList.push_back(
1070 FactOrCheck::getCheck(DT.getNode(&BB), cast<CallInst>(&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 FactOrCheck::getCheck(DT.getNode(&BB), cast<CallInst>(&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.
1083 break;
1084 [[fallthrough]];
1085 case Intrinsic::abs:
1086 WorkList.push_back(FactOrCheck::getInstFact(DT.getNode(&BB), &I));
1087 break;
1088 }
1089
1090 GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I);
1091 }
1092
1093 if (auto *Switch = dyn_cast<SwitchInst>(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(FactOrCheck::getConditionFact(
1100 DT.getNode(Succ), CmpInst::ICMP_EQ, Switch->getCondition(), V));
1101 }
1102 return;
1103 }
1104
1105 auto *Br = dyn_cast<BranchInst>(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(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1))) ||
1115 match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
1116 bool IsOr = match(Cond, m_LogicalOr());
1117 bool IsAnd = match(Cond, 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(IsOr ? 1 : 0);
1124 if (canAddSuccessor(BB, Successor)) {
1125 SmallVector<Value *> CondWorkList;
1126 SmallPtrSet<Value *, 8> SeenCond;
1127 auto QueueValue = [&CondWorkList, &SeenCond](Value *V) {
1128 if (SeenCond.insert(V).second)
1129 CondWorkList.push_back(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>(Cur)) {
1136 WorkList.emplace_back(FactOrCheck::getConditionFact(
1137 DT.getNode(Successor),
1138 IsOr ? CmpInst::getInversePredicate(Cmp->getPredicate())
1139 : Cmp->getPredicate(),
1140 Cmp->getOperand(0), Cmp->getOperand(1)));
1141 continue;
1142 }
1143 if (IsOr && match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) {
1144 QueueValue(Op1);
1145 QueueValue(Op0);
1146 continue;
1147 }
1148 if (IsAnd && match(Cur, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
1149 QueueValue(Op1);
1150 QueueValue(Op0);
1151 continue;
1152 }
1153 }
1154 }
1155 return;
1156 }
1157
1158 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
1159 if (!CmpI)
1160 return;
1161 if (canAddSuccessor(BB, Br->getSuccessor(0)))
1162 WorkList.emplace_back(FactOrCheck::getConditionFact(
1163 DT.getNode(Br->getSuccessor(0)), CmpI->getPredicate(),
1164 CmpI->getOperand(0), CmpI->getOperand(1)));
1165 if (canAddSuccessor(BB, Br->getSuccessor(1)))
1166 WorkList.emplace_back(FactOrCheck::getConditionFact(
1167 DT.getNode(Br->getSuccessor(1)),
1168 CmpInst::getInversePredicate(CmpI->getPredicate()), CmpI->getOperand(0),
1169 CmpI->getOperand(1)));
1170}
1171
1172#ifndef NDEBUG
1174 Value *LHS, Value *RHS) {
1175 OS << "icmp " << Pred << ' ';
1176 LHS->printAsOperand(OS, /*PrintType=*/true);
1177 OS << ", ";
1178 RHS->printAsOperand(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 {
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.
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;
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(IsSigned);
1224 SmallVector<Value *, 4> WorkList(Ops);
1225 while (!WorkList.empty()) {
1226 Value *V = WorkList.pop_back_val();
1227 if (!Seen.insert(V).second)
1228 continue;
1229 if (Old2New.find(V) != Old2New.end())
1230 continue;
1231 if (isa<Constant>(V))
1232 continue;
1233
1234 auto *I = dyn_cast<Instruction>(V);
1235 if (Value2Index.contains(V) || !I ||
1236 !isa<CmpInst, BinaryOperator, GEPOperator, CastInst>(V)) {
1237 Old2New[V] = V;
1238 Args.push_back(V);
1239 LLVM_DEBUG(dbgs() << " found external input " << *V << "\n");
1240 } else {
1241 append_range(WorkList, 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(Entry.Pred));
1249 CollectArguments(Cond, ICmpInst::isSigned(Cond->getPredicate()));
1250
1251 SmallVector<Type *> ParamTys;
1252 for (auto *P : Args)
1253 ParamTys.push_back(P->getType());
1254
1255 FunctionType *FTy = FunctionType::get(Cond->getType(), ParamTys,
1256 /*isVarArg=*/false);
1257 Function *F = Function::Create(FTy, Function::ExternalLinkage,
1258 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)->setName(Args[I]->getName());
1264 Old2New[Args[I]] = F->getArg(I);
1265 }
1266
1267 BasicBlock *Entry = BasicBlock::Create(Ctx, "entry", F);
1268 IRBuilder<> Builder(Entry);
1269 Builder.CreateRet(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);
1279 auto &Value2Index = Info.getValue2Index(IsSigned);
1280 while (!WorkList.empty()) {
1281 Value *V = WorkList.pop_back_val();
1282 if (Old2New.find(V) != Old2New.end())
1283 continue;
1284
1285 auto *I = dyn_cast<Instruction>(V);
1286 if (!Value2Index.contains(V) && I) {
1287 Old2New[V] = nullptr;
1288 ToClone.push_back(I);
1289 append_range(WorkList, I->operands());
1290 }
1291 }
1292
1293 sort(ToClone,
1294 [&DT](Instruction *A, Instruction *B) { return DT.dominates(A, B); });
1295 for (Instruction *I : ToClone) {
1296 Instruction *Cloned = I->clone();
1297 Old2New[I] = Cloned;
1298 Old2New[I]->setName(I->getName());
1299 Cloned->insertBefore(&*Builder.GetInsertPoint());
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(Entry.Pred));
1318
1319 auto *Cmp = Builder.CreateICmp(Entry.Pred, Entry.LHS, Entry.RHS);
1320 Builder.CreateAssumption(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(Cond->getPredicate()));
1326 Entry->getTerminator()->setOperand(0, Cond);
1327 remapInstructionsInBlocks({Entry}, 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, A, 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(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(Row);
1350 auto InfoRestorer = make_scope_exit([&]() {
1351 for (unsigned I = 0; I < R.ExtraInfo.size(); ++I)
1352 CSToUse.popLastConstraint();
1353 });
1354
1355 if (auto ImpliedCondition = R.isImpliedBy(CSToUse)) {
1356 if (!DebugCounter::shouldExecute(EliminatedCounter))
1357 return std::nullopt;
1358
1359 LLVM_DEBUG({
1360 dbgs() << "Condition ";
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
1374 CmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut,
1375 Instruction *ContextInst, Module *ReproducerModule,
1376 ArrayRef<ReproducerEntry> ReproducerCondStack, DominatorTree &DT,
1378 auto ReplaceCmpWithConstant = [&](CmpInst *Cmp, bool IsTrue) {
1379 generateReproducer(Cmp, ReproducerModule, ReproducerCondStack, Info, DT);
1380 Constant *ConstantC = ConstantInt::getBool(
1381 CmpInst::makeCmpResultType(Cmp->getType()), IsTrue);
1382 Cmp->replaceUsesWithIf(ConstantC, [&DT, NumIn, NumOut,
1383 ContextInst](Use &U) {
1384 auto *UserI = getContextInstForUse(U);
1385 auto *DTN = DT.getNode(UserI->getParent());
1386 if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut)
1387 return false;
1388 if (UserI->getParent() == ContextInst->getParent() &&
1389 UserI->comesBefore(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>(U.getUser());
1395 return !II || II->getIntrinsicID() != Intrinsic::assume;
1396 });
1397 NumCondsRemoved++;
1398 if (Cmp->use_empty())
1399 ToRemove.push_back(Cmp);
1400 return true;
1401 };
1402
1403 if (auto ImpliedCondition =
1404 checkCondition(Cmp->getPredicate(), Cmp->getOperand(0),
1405 Cmp->getOperand(1), Cmp, Info))
1406 return ReplaceCmpWithConstant(Cmp, *ImpliedCondition);
1407 return false;
1408}
1409
1410static bool checkAndReplaceMinMax(MinMaxIntrinsic *MinMax, ConstraintInfo &Info,
1412 auto ReplaceMinMaxWithOperand = [&](MinMaxIntrinsic *MinMax, bool UseLHS) {
1413 // TODO: generate reproducer for min/max.
1414 MinMax->replaceAllUsesWith(MinMax->getOperand(UseLHS ? 0 : 1));
1415 ToRemove.push_back(MinMax);
1416 return true;
1417 };
1418
1419 ICmpInst::Predicate Pred =
1420 ICmpInst::getNonStrictPredicate(MinMax->getPredicate());
1421 if (auto ImpliedCondition = checkCondition(
1422 Pred, MinMax->getOperand(0), MinMax->getOperand(1), MinMax, Info))
1423 return ReplaceMinMaxWithOperand(MinMax, *ImpliedCondition);
1424 if (auto ImpliedCondition = checkCondition(
1425 Pred, MinMax->getOperand(1), MinMax->getOperand(0), 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(E.IsSigned);
1436 // Remove variables in the system that went out of scope.
1437 auto &Mapping = Info.getValue2Index(E.IsSigned);
1438 for (Value *V : E.ValuesToRelease)
1439 Mapping.erase(V);
1440 Info.popLastNVariables(E.IsSigned, 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.
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>(CB.getInstructionToSimplify());
1457 unsigned OtherOpIdx = JoinOp->getOperand(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>(JoinOp))
1463 return false;
1464
1465 if (!match(JoinOp->getOperand(OtherOpIdx),
1466 m_ICmp(Pred, m_Value(A), m_Value(B))))
1467 return false;
1468
1469 // For OR, check if the negated condition implies CmpToCheck.
1470 bool IsOr = match(JoinOp, m_LogicalOr());
1471 if (IsOr)
1472 Pred = CmpInst::getInversePredicate(Pred);
1473
1474 // Optimistically add fact from first condition.
1475 unsigned OldSize = DFSInStack.size();
1476 Info.addFact(Pred, A, B, CB.NumIn, 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(CmpToCheck->getPredicate(), CmpToCheck->getOperand(0),
1484 CmpToCheck->getOperand(1), CmpToCheck, Info)) {
1485 if (IsOr && isa<SelectInst>(JoinOp)) {
1486 JoinOp->setOperand(
1487 OtherOpIdx == 0 ? 2 : 0,
1488 ConstantInt::getBool(JoinOp->getType(), *ImpliedCondition));
1489 } else
1490 JoinOp->setOperand(
1491 1 - OtherOpIdx,
1492 ConstantInt::getBool(JoinOp->getType(), *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, A, B, NewVariables);
1513
1514 // TODO: Support non-equality for facts as well.
1515 if (!R.isValid(*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(R.IsSigned);
1522 if (R.Coefficients.empty())
1523 return;
1524
1525 Added |= CSToUse.addVariableRowFill(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(R.IsSigned);
1532 for (Value *V : NewVariables) {
1533 Value2Index.insert({V, Value2Index.size() + 1});
1534 ValuesToRelease.push_back(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(NumIn, NumOut, R.IsSigned,
1544 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(VarPos.Coefficients);
1552 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
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.Coefficients);
1562
1563 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
1565 }
1566 }
1567}
1568
1571 bool Changed = false;
1572 IRBuilder<> Builder(II->getParent(), II->getIterator());
1573 Value *Sub = nullptr;
1574 for (User *U : make_early_inc_range(II->users())) {
1575 if (match(U, m_ExtractValue<0>(m_Value()))) {
1576 if (!Sub)
1577 Sub = Builder.CreateSub(A, B);
1578 U->replaceAllUsesWith(Sub);
1579 Changed = true;
1580 } else if (match(U, m_ExtractValue<1>(m_Value()))) {
1581 U->replaceAllUsesWith(Builder.getFalse());
1582 Changed = true;
1583 } else
1584 continue;
1585
1586 if (U->use_empty()) {
1587 auto *I = cast<Instruction>(U);
1588 ToRemove.push_back(I);
1589 I->setOperand(0, PoisonValue::get(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
1604 auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B,
1605 ConstraintInfo &Info) {
1606 auto R = Info.getConstraintForSolving(Pred, A, B);
1607 if (R.size() < 2 || !R.isValid(Info))
1608 return false;
1609
1610 auto &CSToUse = Info.getCS(R.IsSigned);
1611 return CSToUse.isConditionImplied(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(0);
1619 Value *B = II->getArgOperand(1);
1620 if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) ||
1621 !DoesConditionHold(CmpInst::ICMP_SGE, B,
1622 ConstantInt::get(A->getType(), 0), Info))
1623 return false;
1624 Changed = replaceSubOverflowUses(II, A, B, ToRemove);
1625 }
1626 return Changed;
1627}
1628
1630 ScalarEvolution &SE,
1632 bool Changed = false;
1633 DT.updateDFSNumbers();
1634 SmallVector<Value *> FunctionArgs;
1635 for (Value &Arg : F.args())
1636 FunctionArgs.push_back(&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))
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(S.WorkList, [](const FactOrCheck &A, const FactOrCheck &B) {
1659 auto HasNoConstOp = [](const FactOrCheck &B) {
1660 Value *V0 = B.isConditionFact() ? B.Cond.Op0 : B.Inst->getOperand(0);
1661 Value *V1 = B.isConditionFact() ? B.Cond.Op1 : B.Inst->getOperand(1);
1662 return !isa<ConstantInt>(V0) && !isa<ConstantInt>(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(InstB);
1679 }
1680 return A.NumIn < B.NumIn;
1681 });
1682
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.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>(Inst)) {
1718 Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove);
1719 } else if (auto *Cmp = dyn_cast<ICmpInst>(Inst)) {
1721 Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),
1722 ReproducerModule.get(), ReproducerCondStack, S.DT, ToRemove);
1723 if (!Simplified &&
1724 match(CB.getContextInst(), m_LogicalOp(m_Value(), m_Value()))) {
1725 Simplified =
1726 checkOrAndOpImpliedByOther(CB, Info, ReproducerModule.get(),
1727 ReproducerCondStack, DFSInStack);
1728 }
1729 Changed |= Simplified;
1730 } else if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(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(CmpInst::isSigned(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, CB.NumIn, CB.NumOut, DFSInStack);
1747 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size())
1748 ReproducerCondStack.emplace_back(Pred, A, B);
1749
1750 Info.transferToOtherSystem(Pred, A, B, CB.NumIn, 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(ICmpInst::BAD_ICMP_PREDICATE,
1758 nullptr, nullptr);
1759 }
1760 }
1761 };
1762
1764 if (!CB.isConditionFact()) {
1765 Value *X;
1766 if (match(CB.Inst, m_Intrinsic<Intrinsic::abs>(m_Value(X)))) {
1767 // If is_int_min_poison is true then we may assume llvm.abs >= 0.
1768 if (cast<ConstantInt>(CB.Inst->getOperand(1))->isOne())
1769 AddFact(CmpInst::ICMP_SGE, CB.Inst,
1770 ConstantInt::get(CB.Inst->getType(), 0));
1771 AddFact(CmpInst::ICMP_SGE, CB.Inst, X);
1772 continue;
1773 }
1774
1775 if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(CB.Inst)) {
1776 Pred = ICmpInst::getNonStrictPredicate(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(CB.DoesHold.Pred, CB.DoesHold.Op0, 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(StringS, nullptr);
1813 StringS.flush();
1814 OptimizationRemark Rem(DEBUG_TYPE, "Reproducer", &F);
1815 Rem << ore::NV("module") << S;
1816 ORE.emit(Rem);
1817 }
1818
1819#ifndef NDEBUG
1820 unsigned SignedEntries =
1821 count_if(DFSInStack, [](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
1836 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1837 auto &LI = AM.getResult<LoopAnalysis>(F);
1838 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
1840 if (!eliminateConstraints(F, DT, LI, SE, ORE))
1841 return PreservedAnalyses::all();
1842
1845 PA.preserve<LoopAnalysis>();
1848 return PA;
1849}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
ReachingDefAnalysis InstSet & ToRemove
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
std::pair< ICmpInst *, unsigned > ConditionTy
static int64_t MaxConstraintValue
static int64_t MinSignedConstraintValue
static Instruction * getContextInstForUse(Use &U)
static Decomposition decomposeGEP(GEPOperator &GEP, SmallVectorImpl< ConditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
static bool canUseSExt(ConstantInt *CI)
static int64_t multiplyWithOverflow(int64_t A, int64_t B)
static void dumpConstraint(ArrayRef< int64_t > C, const DenseMap< Value *, unsigned > &Value2Index)
static void removeEntryFromStack(const StackEntry &E, ConstraintInfo &Info, Module *ReproducerModule, SmallVectorImpl< ReproducerEntry > &ReproducerCondStack, SmallVectorImpl< StackEntry > &DFSInStack)
static std::optional< bool > checkCondition(CmpInst::Predicate Pred, Value *A, Value *B, Instruction *CheckInst, ConstraintInfo &Info)
static cl::opt< unsigned > MaxRows("constraint-elimination-max-rows", cl::init(500), cl::Hidden, cl::desc("Maximum number of rows to keep in constraint system"))
static bool eliminateConstraints(Function &F, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, OptimizationRemarkEmitter &ORE)
static int64_t addWithOverflow(int64_t A, int64_t B)
static cl::opt< bool > DumpReproducers("constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden, cl::desc("Dump IR to reproduce successful transformations."))
static OffsetResult collectOffsets(GEPOperator &GEP, const DataLayout &DL)
static bool checkAndReplaceMinMax(MinMaxIntrinsic *MinMax, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
static void generateReproducer(CmpInst *Cond, Module *M, ArrayRef< ReproducerEntry > Stack, ConstraintInfo &Info, DominatorTree &DT)
Helper function to generate a reproducer function for simplifying Cond.
static void dumpUnpackedICmp(raw_ostream &OS, ICmpInst::Predicate Pred, Value *LHS, Value *RHS)
static bool checkOrAndOpImpliedByOther(FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule, SmallVectorImpl< ReproducerEntry > &ReproducerCondStack, SmallVectorImpl< StackEntry > &DFSInStack)
Check if either the first condition of an AND or OR is implied by the (negated in case of OR) second ...
static Decomposition decompose(Value *V, SmallVectorImpl< ConditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
static bool replaceSubOverflowUses(IntrinsicInst *II, Value *A, Value *B, SmallVectorImpl< Instruction * > &ToRemove)
static bool tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
#define DEBUG_TYPE
static bool checkAndReplaceCondition(CmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut, Instruction *ContextInst, Module *ReproducerModule, ArrayRef< ReproducerEntry > ReproducerCondStack, DominatorTree &DT, SmallVectorImpl< Instruction * > &ToRemove)
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
Definition: DebugCounter.h:182
#define LLVM_DEBUG(X)
Definition: Debug.h:101
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1290
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This is the interface for a simple mod/ref and alias analysis over globals.
Hexagon Common GEP
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
if(VerifyEach)
static StringRef getName(Value *V)
const SmallVectorImpl< MachineOperand > & Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:76
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition: APInt.h:1179
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:358
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
Definition: APInt.cpp:1672
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:307
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
Definition: APInt.h:453
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1108
bool isOne() const
Determine if this is a value of 1.
Definition: APInt.h:367
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:198
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:220
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1648
This class represents a function call, abstracting a target machine's calling convention.
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:955
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1323
Predicate getSignedPredicate()
For example, ULT->SLT, ULE->SLE, UGT->SGT, UGE->SGE, SLT->Failed assert.
Definition: InstrTypes.h:1245
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:965
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:994
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:995
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:989
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:988
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:992
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:990
@ ICMP_EQ
equal
Definition: InstrTypes.h:986
@ ICMP_NE
not equal
Definition: InstrTypes.h:987
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:993
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:991
bool isSigned() const
Definition: InstrTypes.h:1226
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:1128
Predicate getUnsignedPredicate()
For example, SLT->ULT, SLE->ULE, SGT->UGT, SGE->UGE, ULT->Failed assert.
Definition: InstrTypes.h:1257
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:1090
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:1066
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
bool isNegative() const
Definition: Constants.h:199
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:159
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:144
static ConstantInt * getBool(LLVMContext &Context, bool V)
Definition: Constants.cpp:863
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:370
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
DenseMap< Value *, unsigned > & getValue2Index()
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
bool isConditionImplied(SmallVector< int64_t, 8 > R) const
static SmallVector< int64_t, 8 > toStrictLessThan(SmallVector< int64_t, 8 > R)
Converts the given vector to form a strict less than inequality.
bool addVariableRow(ArrayRef< int64_t > R)
static SmallVector< int64_t, 8 > negateOrEqual(SmallVector< int64_t, 8 > R)
Multiplies each coefficient in the given vector by -1.
bool addVariableRowFill(ArrayRef< int64_t > R)
void dump() const
Print the constraints in the system.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:72
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
bool erase(const KeyT &Val)
Definition: DenseMap.h:329
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition: DenseMap.h:145
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
unsigned getDFSNumOut() const
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:162
ConstantInt * getTrue()
Get the constant value for i1 true.
Definition: IRBuilder.h:460
BasicBlock::iterator GetInsertPoint() const
Definition: IRBuilder.h:175
ReturnInst * CreateRet(Value *V)
Create a 'ret <val>' instruction.
Definition: IRBuilder.h:1089
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1338
CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles=std::nullopt)
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
Definition: IRBuilder.cpp:551
ConstantInt * getFalse()
Get the constant value for i1 false.
Definition: IRBuilder.h:465
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:180
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2334
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2649
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const BasicBlock * getParent() const
Definition: Instruction.h:151
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:450
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1587
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:54
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:566
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
size_type size() const
Definition: MapVector.h:60
This class represents min/max intrinsics.
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
The optimization diagnostic interface.
Diagnostic information for applied optimization remarks.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1827
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:144
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:129
This class represents an analyzed expression in the program.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
APInt getConstantMultiple(const SCEV *S)
Returns the max constant multiple of S.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:255
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:228
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
Value * getOperand(unsigned i) const
Definition: User.h:169
iterator find(const KeyT &Val)
Definition: ValueMap.h:155
iterator end()
Definition: ValueMap.h:135
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
iterator_range< user_iterator > users()
Definition: Value.h:421
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
Definition: AsmWriter.cpp:5043
const Value * stripPointerCastsSameRepresentation() const
Strip off pointer casts, all-zero GEPs and address space casts but ensures the representation of the ...
Definition: Value.cpp:701
bool use_empty() const
Definition: Value.h:344
self_iterator getIterator()
Definition: ilist_node.h:109
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:660
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
auto m_LogicalOp()
Matches either L && R or L || R where L and R are arbitrary values.
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
DisjointOr_match< LHS, RHS > m_DisjointOr(const LHS &L, const RHS &R)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:163
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
NNegZExt_match< OpTy > m_NNegZExt(const OpTy &Op)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWSub(const LHS &L, const RHS &R)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:92
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
CastInst_match< OpTy, SExtInst > m_SExt(const OpTy &Op)
Matches SExt.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:561
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap > m_NSWMul(const LHS &L, const RHS &R)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
std::enable_if_t< std::is_signed_v< T >, T > MulOverflow(T X, T Y, T &Result)
Multiply two signed integers, computing the two's complement truncated result, returning true if an o...
Definition: MathExtras.h:623
void stable_sort(R &&Range)
Definition: STLExtras.h:2004
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1731
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1689
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
Definition: Verifier.cpp:6966
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2082
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:665
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
constexpr unsigned MaxAnalysisRecursionDepth
Definition: ValueTracking.h:47
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1656
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1858
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:1930
std::enable_if_t< std::is_signed_v< T >, T > AddOverflow(T X, T Y, T &Result)
Add two signed integers, computing the two's complement truncated result, returning true if overflow ...
Definition: MathExtras.h:571
std::enable_if_t< std::is_signed_v< T >, T > SubOverflow(T X, T Y, T &Result)
Subtract two signed integers, computing the two's complement truncated result, returning true if an o...
Definition: MathExtras.h:597
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the give value is known to be non-negative.
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
#define N