LLVM 20.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"
32#include "llvm/IR/Module.h"
34#include "llvm/IR/Verifier.h"
35#include "llvm/Pass.h"
37#include "llvm/Support/Debug.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
57 MaxRows("constraint-elimination-max-rows", cl::init(500), cl::Hidden,
58 cl::desc("Maximum number of rows to keep in constraint system"));
59
61 "constraint-elimination-dump-reproducers", cl::init(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(A, 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(A, B, Result);
78 return Result;
79}
80
82 Instruction *UserI = cast<Instruction>(U.getUser());
83 if (auto *Phi = dyn_cast<PHINode>(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 {
92 Value *Op0;
93 Value *Op1;
94
96 : Pred(CmpInst::BAD_ICMP_PREDICATE), Op0(nullptr), Op1(nullptr) {}
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;
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);
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>(*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;
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(BasicBlockEdge(&BB, Succ), 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
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(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(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;
353
354 Decomposition(int64_t Offset) : Offset(Offset) {}
355 Decomposition(Value *V, bool IsKnownNonNegative = false) {
356 Vars.emplace_back(1, V, 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(Offset, OtherOffset);
363 }
364
365 void add(const Decomposition &Other) {
366 add(Other.Offset);
367 append_range(Vars, Other.Vars);
368 }
369
370 void sub(const Decomposition &Other) {
371 Decomposition Tmp = Other;
372 Tmp.mul(-1);
373 add(Tmp.Offset);
374 append_range(Vars, Tmp.Vars);
375 }
376
377 void mul(int64_t Factor) {
378 Offset = multiplyWithOverflow(Offset, Factor);
379 for (auto &Var : Vars)
380 Var.Coefficient = multiplyWithOverflow(Var.Coefficient, 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(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, Result.VariableOffsets,
407 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>(Result.BasePtr)) {
413 MapVector<Value *, APInt> VariableOffsets2;
414 APInt ConstantOffset2(BitWidth, 0);
415 bool CanCollectInner = InnerGEP->collectOffset(
416 DL, BitWidth, VariableOffsets2, 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();
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(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] =
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(Index, Preconditions, IsSigned, DL);
460 IdxResult.mul(Scale.getSExtValue());
461 Result.add(IdxResult);
462
463 // If Op0 is signed non-negative, the GEP is increasing monotonically and
464 // can be de-composed.
466 Preconditions.emplace_back(CmpInst::ICMP_SGE, Index,
467 ConstantInt::get(Index->getType(), 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(A, Preconditions, IsSigned, DL);
482 auto ResB = decompose(B, Preconditions, IsSignedB, DL);
483 ResA.add(ResB);
484 return ResA;
485 };
486
487 Type *Ty = V->getType()->getScalarType();
488 if (Ty->isPointerTy() && !IsSigned) {
489 if (auto *GEP = dyn_cast<GEPOperator>(V))
490 return decomposeGEP(*GEP, Preconditions, IsSigned, DL);
491 if (isa<ConstantPointerNull>(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>(V)) {
508 if (canUseSExt(CI))
509 return CI->getSExtValue();
510 }
511 Value *Op0;
512 Value *Op1;
513
514 if (match(V, m_SExt(m_Value(Op0))))
515 V = Op0;
516 else if (match(V, m_NNegZExt(m_Value(Op0)))) {
517 V = Op0;
518 IsKnownNonNegative = true;
519 }
520
521 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1))))
522 return MergeResults(Op0, Op1, IsSigned);
523
524 ConstantInt *CI;
525 if (match(V, m_NSWMul(m_Value(Op0), m_ConstantInt(CI))) && canUseSExt(CI)) {
526 auto Result = decompose(Op0, Preconditions, IsSigned, DL);
527 Result.mul(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, m_NSWShl(m_Value(Op0), 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(Op0, Preconditions, IsSigned, DL);
538 Result.mul(int64_t(1) << Shift);
539 return Result;
540 }
541 }
542
543 return {V, IsKnownNonNegative};
544 }
545
546 if (auto *CI = dyn_cast<ConstantInt>(V)) {
547 if (CI->uge(MaxConstraintValue))
548 return V;
549 return int64_t(CI->getZExtValue());
550 }
551
552 Value *Op0;
553 if (match(V, m_ZExt(m_Value(Op0)))) {
554 IsKnownNonNegative = true;
555 V = Op0;
556 }
557
558 if (match(V, m_SExt(m_Value(Op0)))) {
559 V = Op0;
560 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,
561 ConstantInt::get(Op0->getType(), 0));
562 }
563
564 Value *Op1;
565 ConstantInt *CI;
566 if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) {
567 return MergeResults(Op0, Op1, IsSigned);
568 }
569 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) {
570 if (!isKnownNonNegative(Op0, DL))
571 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,
572 ConstantInt::get(Op0->getType(), 0));
573 if (!isKnownNonNegative(Op1, DL))
574 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op1,
575 ConstantInt::get(Op1->getType(), 0));
576
577 return MergeResults(Op0, Op1, IsSigned);
578 }
579
580 if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() &&
581 canUseSExt(CI)) {
582 Preconditions.emplace_back(
584 ConstantInt::get(Op0->getType(), 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, m_DisjointOr(m_Value(Op0), m_ConstantInt(CI))))
590 return MergeResults(Op0, CI, IsSigned);
591
592 if (match(V, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI)) {
593 if (CI->getSExtValue() < 0 || CI->getSExtValue() >= 64)
594 return {V, IsKnownNonNegative};
595 auto Result = decompose(Op1, Preconditions, IsSigned, DL);
596 Result.mul(int64_t{1} << CI->getSExtValue());
597 return Result;
598 }
599
600 if (match(V, m_NUWMul(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI) &&
601 (!CI->isNegative())) {
602 auto Result = decompose(Op1, Preconditions, IsSigned, DL);
603 Result.mul(CI->getSExtValue());
604 return Result;
605 }
606
607 if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1)))) {
608 auto ResA = decompose(Op0, Preconditions, IsSigned, DL);
609 auto ResB = decompose(Op1, Preconditions, IsSigned, DL);
610 ResA.sub(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) {
629 case CmpInst::ICMP_SGE: {
630 Pred = CmpInst::getSwappedPredicate(Pred);
631 std::swap(Op0, Op1);
632 break;
633 }
634 case CmpInst::ICMP_EQ:
635 if (match(Op1, 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(Op1, m_Zero())) {
645 std::swap(Op0, 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(Pred);
661 auto &Value2Index = getValue2Index(IsSigned);
663 Preconditions, IsSigned, DL);
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.
676 auto GetOrAddIndex = [&Value2Index, &NewVariables,
677 &NewIndexMap](Value *V) -> unsigned {
678 auto V2I = Value2Index.find(V);
679 if (V2I != Value2Index.end())
680 return V2I->second;
681 auto Insert =
682 NewIndexMap.insert({V, Value2Index.size() + NewVariables.size() + 1});
683 if (Insert.second)
684 NewVariables.push_back(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>(VariablesA, 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.Variable, KV.IsKnownNonNegative});
705 I.first->second &= KV.IsKnownNonNegative;
706 }
707
708 for (const auto &KV : VariablesB) {
709 if (SubOverflow(R[GetOrAddIndex(KV.Variable)], KV.Coefficient,
710 R[GetOrAddIndex(KV.Variable)]))
711 return {};
712 auto I =
713 KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative});
714 I.first->second &= KV.IsKnownNonNegative;
715 }
716
717 int64_t OffsetSum;
718 if (AddOverflow(Offset1, Offset2, OffsetSum))
719 return {};
720 if (Pred == (IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT))
721 if (AddOverflow(OffsetSum, int64_t(-1), 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(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(KV.first) && !NewIndexMap.contains(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(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(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(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(Pred) &&
767 isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1) &&
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(Preconditions, [&Info](const ConditionTy &C) {
781 return Info.doesHold(C.Pred, C.Op0, C.Op1);
782 });
783}
784
785std::optional<bool>
786ConstraintTy::isImpliedBy(const ConstraintSystem &CS) const {
787 bool IsConditionImplied = CS.isConditionImplied(Coefficients);
788
789 if (IsEq || IsNe) {
790 auto NegatedOrEqual = ConstraintSystem::negateOrEqual(Coefficients);
791 bool IsNegatedOrEqualImplied =
792 !NegatedOrEqual.empty() && CS.isConditionImplied(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(Coefficients);
801 bool IsNegatedImplied = !Negated.empty() && CS.isConditionImplied(Negated);
802
803 auto StrictLessThan = ConstraintSystem::toStrictLessThan(Coefficients);
804 bool IsStrictLessThanImplied =
805 !StrictLessThan.empty() && CS.isConditionImplied(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(Coefficients);
821 auto IsNegatedImplied = !Negated.empty() && CS.isConditionImplied(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, A, B);
832 return R.isValid(*this) &&
833 getCS(R.IsSigned).isConditionImplied(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(CmpInst::ICMP_SGE, V, ConstantInt::get(V->getType(), 0)) ||
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;
855 // If B is a signed positive constant, then A >=s 0 and A <s (or <=s) B.
856 if (IsKnownNonNegative(B)) {
857 addFact(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0), NumIn,
858 NumOut, DFSInStack);
859 addFact(CmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut,
860 DFSInStack);
861 }
862 break;
865 // If A is a signed positive constant, then B >=s 0 and A >s (or >=s) B.
866 if (IsKnownNonNegative(A)) {
867 addFact(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0), NumIn,
868 NumOut, DFSInStack);
869 addFact(CmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut,
870 DFSInStack);
871 }
872 break;
874 if (IsKnownNonNegative(A))
875 addFact(CmpInst::ICMP_ULT, A, B, NumIn, NumOut, DFSInStack);
876 break;
877 case CmpInst::ICMP_SGT: {
878 if (doesHold(CmpInst::ICMP_SGE, B, Constant::getAllOnesValue(B->getType())))
879 addFact(CmpInst::ICMP_UGE, A, ConstantInt::get(B->getType(), 0), NumIn,
880 NumOut, DFSInStack);
881 if (IsKnownNonNegative(B))
882 addFact(CmpInst::ICMP_UGT, A, B, NumIn, NumOut, DFSInStack);
883
884 break;
885 }
887 if (IsKnownNonNegative(B))
888 addFact(CmpInst::ICMP_UGE, A, B, NumIn, NumOut, DFSInStack);
889 break;
890 }
891}
892
893#ifndef NDEBUG
894
896 const DenseMap<Value *, unsigned> &Value2Index) {
897 ConstraintSystem CS(Value2Index);
899 CS.dump();
900}
901#endif
902
903void State::addInfoForInductions(BasicBlock &BB) {
904 auto *L = LI.getLoopFor(&BB);
905 if (!L || L->getHeader() != &BB)
906 return;
907
908 Value *A;
909 Value *B;
911
912 if (!match(BB.getTerminator(),
913 m_Br(m_ICmp(Pred, m_Value(A), m_Value(B)), m_Value(), m_Value())))
914 return;
915 PHINode *PN = dyn_cast<PHINode>(A);
916 if (!PN) {
917 Pred = CmpInst::getSwappedPredicate(Pred);
918 std::swap(A, B);
919 PN = dyn_cast<PHINode>(A);
920 }
921
922 if (!PN || PN->getParent() != &BB || PN->getNumIncomingValues() != 2 ||
923 !SE.isSCEVable(PN->getType()))
924 return;
925
926 BasicBlock *InLoopSucc = nullptr;
927 if (Pred == CmpInst::ICMP_NE)
928 InLoopSucc = cast<BranchInst>(BB.getTerminator())->getSuccessor(0);
929 else if (Pred == CmpInst::ICMP_EQ)
930 InLoopSucc = cast<BranchInst>(BB.getTerminator())->getSuccessor(1);
931 else
932 return;
933
934 if (!L->contains(InLoopSucc) || !L->isLoopExiting(&BB) || InLoopSucc == &BB)
935 return;
936
937 auto *AR = dyn_cast_or_null<SCEVAddRecExpr>(SE.getSCEV(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>(StartSCEV)) {
945 StartValue = C->getValue();
946 } else {
947 StartValue = PN->getIncomingValueForBlock(LoopPred);
948 assert(SE.getSCEV(StartValue) == StartSCEV && "inconsistent start value");
949 }
950
951 DomTreeNode *DTN = DT.getNode(InLoopSucc);
952 auto IncUnsigned = SE.getMonotonicPredicateType(AR, CmpInst::ICMP_UGT);
953 auto IncSigned = SE.getMonotonicPredicateType(AR, 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 FactOrCheck::getConditionFact(DTN, CmpInst::ICMP_UGE, PN, StartValue));
963 if (MonotonicallyIncreasingSigned)
964 WorkList.push_back(
965 FactOrCheck::getConditionFact(DTN, CmpInst::ICMP_SGE, PN, StartValue));
966
967 APInt StepOffset;
968 if (auto *C = dyn_cast<SCEVConstant>(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(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(FactOrCheck::getConditionFact(
987 DTN, CmpInst::ICMP_UGE, StartValue, PN,
988 ConditionTy(CmpInst::ICMP_ULE, B, StartValue)));
989 WorkList.push_back(FactOrCheck::getConditionFact(
990 DTN, CmpInst::ICMP_SGE, StartValue, PN,
991 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(FactOrCheck::getConditionFact(
995 DTN, CmpInst::ICMP_UGT, PN, B,
996 ConditionTy(CmpInst::ICMP_ULE, B, StartValue)));
997 WorkList.push_back(FactOrCheck::getConditionFact(
998 DTN, CmpInst::ICMP_SGT, PN, B,
999 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(SE.getSCEV(B), StartSCEV);
1012 if (isa<SCEVCouldNotCompute>(BMinusStart) ||
1013 !SE.getConstantMultiple(BMinusStart).urem(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(FactOrCheck::getConditionFact(
1022 DTN, CmpInst::ICMP_UGE, PN, StartValue,
1023 ConditionTy(CmpInst::ICMP_ULE, StartValue, B)));
1024 if (!MonotonicallyIncreasingSigned)
1025 WorkList.push_back(FactOrCheck::getConditionFact(
1026 DTN, CmpInst::ICMP_SGE, PN, StartValue,
1027 ConditionTy(CmpInst::ICMP_SLE, StartValue, B)));
1028
1029 WorkList.push_back(FactOrCheck::getConditionFact(
1030 DTN, CmpInst::ICMP_ULT, PN, B,
1031 ConditionTy(CmpInst::ICMP_ULE, StartValue, B)));
1032 WorkList.push_back(FactOrCheck::getConditionFact(
1033 DTN, CmpInst::ICMP_SLT, PN, B,
1034 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};
1044 L->getExitBlocks(ExitBBs);
1045 for (BasicBlock *EB : ExitBBs) {
1046 WorkList.emplace_back(FactOrCheck::getConditionFact(
1047 DT.getNode(EB), CmpInst::ICMP_ULE, A, 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>(&I)) {
1059 for (Use &U : Cmp->uses()) {
1060 auto *UserI = getContextInstForUse(U);
1061 auto *DTN = DT.getNode(UserI->getParent());
1062 if (!DTN)
1063 continue;
1064 WorkList.push_back(FactOrCheck::getCheck(DTN, &U));
1065 }
1066 continue;
1067 }
1068
1069 auto *II = dyn_cast<IntrinsicInst>(&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(I.getOperand(0), m_ICmp(Pred, m_Value(A), m_Value(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(FactOrCheck::getConditionFact(
1081 DT.getNode(I.getParent()), Pred, A, B));
1082 } else {
1083 WorkList.emplace_back(
1084 FactOrCheck::getInstFact(DT.getNode(I.getParent()), &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 FactOrCheck::getCheck(DT.getNode(&BB), cast<CallInst>(&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 FactOrCheck::getCheck(DT.getNode(&BB), cast<CallInst>(&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.
1106 break;
1107 [[fallthrough]];
1108 case Intrinsic::abs:
1109 WorkList.push_back(FactOrCheck::getInstFact(DT.getNode(&BB), &I));
1110 break;
1111 }
1112
1113 GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I);
1114 }
1115
1116 if (auto *Switch = dyn_cast<SwitchInst>(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(FactOrCheck::getConditionFact(
1123 DT.getNode(Succ), CmpInst::ICMP_EQ, Switch->getCondition(), V));
1124 }
1125 return;
1126 }
1127
1128 auto *Br = dyn_cast<BranchInst>(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(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1))) ||
1138 match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
1139 bool IsOr = match(Cond, m_LogicalOr());
1140 bool IsAnd = match(Cond, 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(IsOr ? 1 : 0);
1147 if (canAddSuccessor(BB, Successor)) {
1148 SmallVector<Value *> CondWorkList;
1149 SmallPtrSet<Value *, 8> SeenCond;
1150 auto QueueValue = [&CondWorkList, &SeenCond](Value *V) {
1151 if (SeenCond.insert(V).second)
1152 CondWorkList.push_back(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>(Cur)) {
1159 WorkList.emplace_back(FactOrCheck::getConditionFact(
1160 DT.getNode(Successor),
1161 IsOr ? CmpInst::getInversePredicate(Cmp->getPredicate())
1162 : Cmp->getPredicate(),
1163 Cmp->getOperand(0), Cmp->getOperand(1)));
1164 continue;
1165 }
1166 if (IsOr && match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) {
1167 QueueValue(Op1);
1168 QueueValue(Op0);
1169 continue;
1170 }
1171 if (IsAnd && match(Cur, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
1172 QueueValue(Op1);
1173 QueueValue(Op0);
1174 continue;
1175 }
1176 }
1177 }
1178 return;
1179 }
1180
1181 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
1182 if (!CmpI)
1183 return;
1184 if (canAddSuccessor(BB, Br->getSuccessor(0)))
1185 WorkList.emplace_back(FactOrCheck::getConditionFact(
1186 DT.getNode(Br->getSuccessor(0)), CmpI->getPredicate(),
1187 CmpI->getOperand(0), CmpI->getOperand(1)));
1188 if (canAddSuccessor(BB, Br->getSuccessor(1)))
1189 WorkList.emplace_back(FactOrCheck::getConditionFact(
1190 DT.getNode(Br->getSuccessor(1)),
1191 CmpInst::getInversePredicate(CmpI->getPredicate()), CmpI->getOperand(0),
1192 CmpI->getOperand(1)));
1193}
1194
1195#ifndef NDEBUG
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 {
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.
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;
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(IsSigned);
1247 SmallVector<Value *, 4> WorkList(Ops);
1248 while (!WorkList.empty()) {
1249 Value *V = WorkList.pop_back_val();
1250 if (!Seen.insert(V).second)
1251 continue;
1252 if (Old2New.find(V) != Old2New.end())
1253 continue;
1254 if (isa<Constant>(V))
1255 continue;
1256
1257 auto *I = dyn_cast<Instruction>(V);
1258 if (Value2Index.contains(V) || !I ||
1259 !isa<CmpInst, BinaryOperator, GEPOperator, CastInst>(V)) {
1260 Old2New[V] = V;
1261 Args.push_back(V);
1262 LLVM_DEBUG(dbgs() << " found external input " << *V << "\n");
1263 } else {
1264 append_range(WorkList, 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(Entry.Pred));
1272 CollectArguments(Cond, ICmpInst::isSigned(Cond->getPredicate()));
1273
1274 SmallVector<Type *> ParamTys;
1275 for (auto *P : Args)
1276 ParamTys.push_back(P->getType());
1277
1278 FunctionType *FTy = FunctionType::get(Cond->getType(), ParamTys,
1279 /*isVarArg=*/false);
1280 Function *F = Function::Create(FTy, Function::ExternalLinkage,
1281 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)->setName(Args[I]->getName());
1287 Old2New[Args[I]] = F->getArg(I);
1288 }
1289
1290 BasicBlock *Entry = BasicBlock::Create(Ctx, "entry", F);
1291 IRBuilder<> Builder(Entry);
1292 Builder.CreateRet(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);
1302 auto &Value2Index = Info.getValue2Index(IsSigned);
1303 while (!WorkList.empty()) {
1304 Value *V = WorkList.pop_back_val();
1305 if (Old2New.find(V) != Old2New.end())
1306 continue;
1307
1308 auto *I = dyn_cast<Instruction>(V);
1309 if (!Value2Index.contains(V) && I) {
1310 Old2New[V] = nullptr;
1311 ToClone.push_back(I);
1312 append_range(WorkList, I->operands());
1313 }
1314 }
1315
1316 sort(ToClone,
1317 [&DT](Instruction *A, Instruction *B) { return DT.dominates(A, B); });
1318 for (Instruction *I : ToClone) {
1319 Instruction *Cloned = I->clone();
1320 Old2New[I] = Cloned;
1321 Old2New[I]->setName(I->getName());
1322 Cloned->insertBefore(&*Builder.GetInsertPoint());
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(Entry.Pred));
1341
1342 auto *Cmp = Builder.CreateICmp(Entry.Pred, Entry.LHS, Entry.RHS);
1343 Builder.CreateAssumption(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(Cond->getPredicate()));
1349 Entry->getTerminator()->setOperand(0, Cond);
1350 remapInstructionsInBlocks({Entry}, 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, A, 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(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(Row);
1373 auto InfoRestorer = make_scope_exit([&]() {
1374 for (unsigned I = 0; I < R.ExtraInfo.size(); ++I)
1375 CSToUse.popLastConstraint();
1376 });
1377
1378 if (auto ImpliedCondition = R.isImpliedBy(CSToUse)) {
1379 if (!DebugCounter::shouldExecute(EliminatedCounter))
1380 return std::nullopt;
1381
1382 LLVM_DEBUG({
1383 dbgs() << "Condition ";
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
1397 CmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut,
1398 Instruction *ContextInst, Module *ReproducerModule,
1399 ArrayRef<ReproducerEntry> ReproducerCondStack, DominatorTree &DT,
1401 auto ReplaceCmpWithConstant = [&](CmpInst *Cmp, bool IsTrue) {
1402 generateReproducer(Cmp, ReproducerModule, ReproducerCondStack, Info, DT);
1403 Constant *ConstantC = ConstantInt::getBool(
1404 CmpInst::makeCmpResultType(Cmp->getType()), IsTrue);
1405 Cmp->replaceUsesWithIf(ConstantC, [&DT, NumIn, NumOut,
1406 ContextInst](Use &U) {
1407 auto *UserI = getContextInstForUse(U);
1408 auto *DTN = DT.getNode(UserI->getParent());
1409 if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut)
1410 return false;
1411 if (UserI->getParent() == ContextInst->getParent() &&
1412 UserI->comesBefore(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>(U.getUser());
1418 return !II || II->getIntrinsicID() != Intrinsic::assume;
1419 });
1420 NumCondsRemoved++;
1421 if (Cmp->use_empty())
1422 ToRemove.push_back(Cmp);
1423 return true;
1424 };
1425
1426 if (auto ImpliedCondition =
1427 checkCondition(Cmp->getPredicate(), Cmp->getOperand(0),
1428 Cmp->getOperand(1), Cmp, Info))
1429 return ReplaceCmpWithConstant(Cmp, *ImpliedCondition);
1430 return false;
1431}
1432
1433static bool checkAndReplaceMinMax(MinMaxIntrinsic *MinMax, ConstraintInfo &Info,
1435 auto ReplaceMinMaxWithOperand = [&](MinMaxIntrinsic *MinMax, bool UseLHS) {
1436 // TODO: generate reproducer for min/max.
1437 MinMax->replaceAllUsesWith(MinMax->getOperand(UseLHS ? 0 : 1));
1438 ToRemove.push_back(MinMax);
1439 return true;
1440 };
1441
1442 ICmpInst::Predicate Pred =
1443 ICmpInst::getNonStrictPredicate(MinMax->getPredicate());
1444 if (auto ImpliedCondition = checkCondition(
1445 Pred, MinMax->getOperand(0), MinMax->getOperand(1), MinMax, Info))
1446 return ReplaceMinMaxWithOperand(MinMax, *ImpliedCondition);
1447 if (auto ImpliedCondition = checkCondition(
1448 Pred, MinMax->getOperand(1), MinMax->getOperand(0), MinMax, Info))
1449 return ReplaceMinMaxWithOperand(MinMax, !*ImpliedCondition);
1450 return false;
1451}
1452
1453static bool checkAndReplaceCmp(CmpIntrinsic *I, ConstraintInfo &Info,
1455 Value *LHS = I->getOperand(0);
1456 Value *RHS = I->getOperand(1);
1457 if (checkCondition(I->getGTPredicate(), LHS, RHS, I, Info).value_or(false)) {
1458 I->replaceAllUsesWith(ConstantInt::get(I->getType(), 1));
1459 ToRemove.push_back(I);
1460 return true;
1461 }
1462 if (checkCondition(I->getLTPredicate(), LHS, RHS, I, Info).value_or(false)) {
1463 I->replaceAllUsesWith(ConstantInt::getSigned(I->getType(), -1));
1464 ToRemove.push_back(I);
1465 return true;
1466 }
1467 if (checkCondition(ICmpInst::ICMP_EQ, LHS, RHS, I, Info)) {
1468 I->replaceAllUsesWith(ConstantInt::get(I->getType(), 0));
1469 ToRemove.push_back(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(E.IsSigned);
1481 // Remove variables in the system that went out of scope.
1482 auto &Mapping = Info.getValue2Index(E.IsSigned);
1483 for (Value *V : E.ValuesToRelease)
1484 Mapping.erase(V);
1485 Info.popLastNVariables(E.IsSigned, 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.
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>(CB.getInstructionToSimplify());
1502 unsigned OtherOpIdx = JoinOp->getOperand(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>(JoinOp))
1508 return false;
1509
1510 if (!match(JoinOp->getOperand(OtherOpIdx),
1511 m_ICmp(Pred, m_Value(A), m_Value(B))))
1512 return false;
1513
1514 // For OR, check if the negated condition implies CmpToCheck.
1515 bool IsOr = match(JoinOp, m_LogicalOr());
1516 if (IsOr)
1517 Pred = CmpInst::getInversePredicate(Pred);
1518
1519 // Optimistically add fact from first condition.
1520 unsigned OldSize = DFSInStack.size();
1521 Info.addFact(Pred, A, B, CB.NumIn, 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(CmpToCheck->getPredicate(), CmpToCheck->getOperand(0),
1529 CmpToCheck->getOperand(1), CmpToCheck, Info)) {
1530 if (IsOr && isa<SelectInst>(JoinOp)) {
1531 JoinOp->setOperand(
1532 OtherOpIdx == 0 ? 2 : 0,
1533 ConstantInt::getBool(JoinOp->getType(), *ImpliedCondition));
1534 } else
1535 JoinOp->setOperand(
1536 1 - OtherOpIdx,
1537 ConstantInt::getBool(JoinOp->getType(), *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, A, B, NewVariables);
1558
1559 // TODO: Support non-equality for facts as well.
1560 if (!R.isValid(*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(R.IsSigned);
1567 if (R.Coefficients.empty())
1568 return;
1569
1570 Added |= CSToUse.addVariableRowFill(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(R.IsSigned);
1577 for (Value *V : NewVariables) {
1578 Value2Index.insert({V, Value2Index.size() + 1});
1579 ValuesToRelease.push_back(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(NumIn, NumOut, R.IsSigned,
1589 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(VarPos.Coefficients);
1597 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
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.Coefficients);
1607
1608 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
1610 }
1611 }
1612}
1613
1616 bool Changed = false;
1617 IRBuilder<> Builder(II->getParent(), II->getIterator());
1618 Value *Sub = nullptr;
1619 for (User *U : make_early_inc_range(II->users())) {
1620 if (match(U, m_ExtractValue<0>(m_Value()))) {
1621 if (!Sub)
1622 Sub = Builder.CreateSub(A, B);
1623 U->replaceAllUsesWith(Sub);
1624 Changed = true;
1625 } else if (match(U, m_ExtractValue<1>(m_Value()))) {
1626 U->replaceAllUsesWith(Builder.getFalse());
1627 Changed = true;
1628 } else
1629 continue;
1630
1631 if (U->use_empty()) {
1632 auto *I = cast<Instruction>(U);
1633 ToRemove.push_back(I);
1634 I->setOperand(0, PoisonValue::get(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
1649 auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B,
1650 ConstraintInfo &Info) {
1651 auto R = Info.getConstraintForSolving(Pred, A, B);
1652 if (R.size() < 2 || !R.isValid(Info))
1653 return false;
1654
1655 auto &CSToUse = Info.getCS(R.IsSigned);
1656 return CSToUse.isConditionImplied(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(0);
1664 Value *B = II->getArgOperand(1);
1665 if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) ||
1666 !DoesConditionHold(CmpInst::ICMP_SGE, B,
1667 ConstantInt::get(A->getType(), 0), Info))
1668 return false;
1669 Changed = replaceSubOverflowUses(II, A, B, ToRemove);
1670 }
1671 return Changed;
1672}
1673
1675 ScalarEvolution &SE,
1677 bool Changed = false;
1678 DT.updateDFSNumbers();
1679 SmallVector<Value *> FunctionArgs;
1680 for (Value &Arg : F.args())
1681 FunctionArgs.push_back(&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))
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(S.WorkList, [](const FactOrCheck &A, const FactOrCheck &B) {
1704 auto HasNoConstOp = [](const FactOrCheck &B) {
1705 Value *V0 = B.isConditionFact() ? B.Cond.Op0 : B.Inst->getOperand(0);
1706 Value *V1 = B.isConditionFact() ? B.Cond.Op1 : B.Inst->getOperand(1);
1707 return !isa<ConstantInt>(V0) && !isa<ConstantInt>(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(InstB);
1724 }
1725 return A.NumIn < B.NumIn;
1726 });
1727
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.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>(Inst)) {
1763 Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove);
1764 } else if (auto *Cmp = dyn_cast<ICmpInst>(Inst)) {
1766 Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),
1767 ReproducerModule.get(), ReproducerCondStack, S.DT, ToRemove);
1768 if (!Simplified &&
1769 match(CB.getContextInst(), m_LogicalOp(m_Value(), m_Value()))) {
1770 Simplified =
1771 checkOrAndOpImpliedByOther(CB, Info, ReproducerModule.get(),
1772 ReproducerCondStack, DFSInStack);
1773 }
1774 Changed |= Simplified;
1775 } else if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(Inst)) {
1776 Changed |= checkAndReplaceMinMax(MinMax, Info, ToRemove);
1777 } else if (auto *CmpIntr = dyn_cast<CmpIntrinsic>(Inst)) {
1778 Changed |= checkAndReplaceCmp(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(CmpInst::isSigned(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, CB.NumIn, CB.NumOut, DFSInStack);
1794 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size())
1795 ReproducerCondStack.emplace_back(Pred, A, B);
1796
1797 Info.transferToOtherSystem(Pred, A, B, CB.NumIn, 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(ICmpInst::BAD_ICMP_PREDICATE,
1805 nullptr, nullptr);
1806 }
1807 }
1808 };
1809
1811 if (!CB.isConditionFact()) {
1812 Value *X;
1813 if (match(CB.Inst, m_Intrinsic<Intrinsic::abs>(m_Value(X)))) {
1814 // If is_int_min_poison is true then we may assume llvm.abs >= 0.
1815 if (cast<ConstantInt>(CB.Inst->getOperand(1))->isOne())
1816 AddFact(CmpInst::ICMP_SGE, CB.Inst,
1817 ConstantInt::get(CB.Inst->getType(), 0));
1818 AddFact(CmpInst::ICMP_SGE, CB.Inst, X);
1819 continue;
1820 }
1821
1822 if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(CB.Inst)) {
1823 Pred = ICmpInst::getNonStrictPredicate(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(CB.DoesHold.Pred, CB.DoesHold.Op0, 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(CB.Inst, m_Intrinsic<Intrinsic::assume>(
1849 m_ICmp(Pred, m_Value(A), m_Value(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(StringS, nullptr);
1860 StringS.flush();
1861 OptimizationRemark Rem(DEBUG_TYPE, "Reproducer", &F);
1862 Rem << ore::NV("module") << S;
1863 ORE.emit(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
1883 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1884 auto &LI = AM.getResult<LoopAnalysis>(F);
1885 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
1887 if (!eliminateConstraints(F, DT, LI, SE, ORE))
1888 return PreservedAnalyses::all();
1889
1892 PA.preserve<LoopAnalysis>();
1895 return PA;
1896}
ReachingDefAnalysis InstSet & ToRemove
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
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)
static bool checkAndReplaceCmp(CmpIntrinsic *I, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
Definition: DebugCounter.h:190
#define LLVM_DEBUG(X)
Definition: Debug.h:101
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1309
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
Module.h This file contains the declarations for the Module class.
uint64_t IntrinsicInst * II
#define P(N)
if(PassOpts->AAPipeline)
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:166
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:78
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:1636
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:253
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:405
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:61
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:212
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:239
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:72
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:747
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1104
Predicate getSignedPredicate()
For example, ULT->SLT, ULE->SLE, UGT->SGT, UGE->SGE, SLT->Failed assert.
Definition: InstrTypes.h:1026
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:757
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:786
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:787
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:781
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:780
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:784
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:782
@ ICMP_EQ
equal
Definition: InstrTypes.h:778
@ ICMP_NE
not equal
Definition: InstrTypes.h:779
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:785
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:783
bool isSigned() const
Definition: InstrTypes.h:1007
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:909
Predicate getUnsignedPredicate()
For example, SLT->ULT, SLE->ULE, SGT->UGT, SGE->UGE, ULT->Failed assert.
Definition: InstrTypes.h:1038
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:871
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:847
This class represents a ucmp/scmp intrinsic.
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
bool isNegative() const
Definition: Constants.h:201
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
Definition: Constants.h:124
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:161
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:146
static ConstantInt * getBool(LLVMContext &Context, bool V)
Definition: Constants.cpp:864
This is an important base class in LLVM.
Definition: Constant.h:42
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:417
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:63
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:87
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
bool erase(const KeyT &Val)
Definition: DenseMap.h:336
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition: DenseMap.h:146
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:211
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:172
ConstantInt * getTrue()
Get the constant value for i1 true.
Definition: IRBuilder.h:463
BasicBlock::iterator GetInsertPoint() const
Definition: IRBuilder.h:172
ReturnInst * CreateRet(Value *V)
Create a 'ret <val>' instruction.
Definition: IRBuilder.h:1112
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1361
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:552
ConstantInt * getFalse()
Get the constant value for i1 false.
Definition: IRBuilder.h:468
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:177
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2371
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2686
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:97
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs=std::nullopt)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1596
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:463
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:48
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:1852
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:146
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:131
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:367
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:502
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:251
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:224
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
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:5106
const Value * stripPointerCastsSameRepresentation() const
Strip off pointer casts, all-zero GEPs and address space casts but ensures the representation of the ...
Definition: Value.cpp:702
const ParentTy * getParent() const
Definition: ilist_node.h:32
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:661
@ 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:168
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:612
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:443
@ 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:753
void stable_sort(R &&Range)
Definition: STLExtras.h:2020
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:1722
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:1680
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:7137
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2098
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:656
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:44
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1647
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:1856
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:1928
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:701
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:727
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