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