LLVM 22.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"
28#include "llvm/IR/DataLayout.h"
29#include "llvm/IR/DebugInfo.h"
30#include "llvm/IR/Dominators.h"
31#include "llvm/IR/Function.h"
32#include "llvm/IR/IRBuilder.h"
33#include "llvm/IR/InstrTypes.h"
35#include "llvm/IR/Module.h"
37#include "llvm/IR/Verifier.h"
38#include "llvm/Pass.h"
40#include "llvm/Support/Debug.h"
45
46#include <optional>
47#include <string>
48
49using namespace llvm;
50using namespace PatternMatch;
51
52#define DEBUG_TYPE "constraint-elimination"
53
54STATISTIC(NumCondsRemoved, "Number of instructions removed");
55DEBUG_COUNTER(EliminatedCounter, "conds-eliminated",
56 "Controls which conditions are eliminated");
57
59 MaxRows("constraint-elimination-max-rows", cl::init(500), cl::Hidden,
60 cl::desc("Maximum number of rows to keep in constraint system"));
61
63 "constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden,
64 cl::desc("Dump IR to reproduce successful transformations."));
65
66static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max();
67static int64_t MinSignedConstraintValue = std::numeric_limits<int64_t>::min();
68
70 Instruction *UserI = cast<Instruction>(U.getUser());
71 if (auto *Phi = dyn_cast<PHINode>(UserI))
72 UserI = Phi->getIncomingBlock(U)->getTerminator();
73 return UserI;
74}
75
76namespace {
77/// Struct to express a condition of the form %Op0 Pred %Op1.
78struct ConditionTy {
79 CmpPredicate Pred;
80 Value *Op0 = nullptr;
81 Value *Op1 = nullptr;
82
83 ConditionTy() = default;
84 ConditionTy(CmpPredicate Pred, Value *Op0, Value *Op1)
85 : Pred(Pred), Op0(Op0), Op1(Op1) {}
86};
87
88/// Represents either
89/// * a condition that holds on entry to a block (=condition fact)
90/// * an assume (=assume fact)
91/// * a use of a compare instruction to simplify.
92/// It also tracks the Dominator DFS in and out numbers for each entry.
93struct FactOrCheck {
94 enum class EntryTy {
95 ConditionFact, /// A condition that holds on entry to a block.
96 InstFact, /// A fact that holds after Inst executed (e.g. an assume or
97 /// min/mix intrinsic.
98 InstCheck, /// An instruction to simplify (e.g. an overflow math
99 /// intrinsics).
100 UseCheck /// An use of a compare instruction to simplify.
101 };
102
103 union {
104 Instruction *Inst;
105 Use *U;
107 };
108
109 /// A pre-condition that must hold for the current fact to be added to the
110 /// system.
111 ConditionTy DoesHold;
112
113 unsigned NumIn;
114 unsigned NumOut;
115 EntryTy Ty;
116
117 FactOrCheck(EntryTy Ty, DomTreeNode *DTN, Instruction *Inst)
118 : Inst(Inst), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
119 Ty(Ty) {}
120
121 FactOrCheck(DomTreeNode *DTN, Use *U)
122 : U(U), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
123 Ty(EntryTy::UseCheck) {}
124
125 FactOrCheck(DomTreeNode *DTN, CmpPredicate Pred, Value *Op0, Value *Op1,
126 ConditionTy Precond = {})
127 : Cond(Pred, Op0, Op1), DoesHold(Precond), NumIn(DTN->getDFSNumIn()),
128 NumOut(DTN->getDFSNumOut()), Ty(EntryTy::ConditionFact) {}
129
130 static FactOrCheck getConditionFact(DomTreeNode *DTN, CmpPredicate Pred,
131 Value *Op0, Value *Op1,
132 ConditionTy Precond = {}) {
133 return FactOrCheck(DTN, Pred, Op0, Op1, Precond);
134 }
135
136 static FactOrCheck getInstFact(DomTreeNode *DTN, Instruction *Inst) {
137 return FactOrCheck(EntryTy::InstFact, DTN, Inst);
138 }
139
140 static FactOrCheck getCheck(DomTreeNode *DTN, Use *U) {
141 return FactOrCheck(DTN, U);
142 }
143
144 static FactOrCheck getCheck(DomTreeNode *DTN, CallInst *CI) {
145 return FactOrCheck(EntryTy::InstCheck, DTN, CI);
146 }
147
148 bool isCheck() const {
149 return Ty == EntryTy::InstCheck || Ty == EntryTy::UseCheck;
150 }
151
152 Instruction *getContextInst() const {
153 assert(!isConditionFact());
154 if (Ty == EntryTy::UseCheck)
155 return getContextInstForUse(*U);
156 return Inst;
157 }
158
159 Instruction *getInstructionToSimplify() const {
160 assert(isCheck());
161 if (Ty == EntryTy::InstCheck)
162 return Inst;
163 // The use may have been simplified to a constant already.
164 return dyn_cast<Instruction>(*U);
165 }
166
167 bool isConditionFact() const { return Ty == EntryTy::ConditionFact; }
168};
169
170/// Keep state required to build worklist.
171struct State {
172 DominatorTree &DT;
173 LoopInfo &LI;
174 ScalarEvolution &SE;
177
178 State(DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE,
180 : DT(DT), LI(LI), SE(SE), TLI(TLI) {}
181
182 /// Process block \p BB and add known facts to work-list.
183 void addInfoFor(BasicBlock &BB);
184
185 /// Try to add facts for loop inductions (AddRecs) in EQ/NE compares
186 /// controlling the loop header.
187 void addInfoForInductions(BasicBlock &BB);
188
189 /// Returns true if we can add a known condition from BB to its successor
190 /// block Succ.
191 bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ) const {
192 return DT.dominates(BasicBlockEdge(&BB, Succ), Succ);
193 }
194};
195
196class ConstraintInfo;
197
198struct StackEntry {
199 unsigned NumIn;
200 unsigned NumOut;
201 bool IsSigned = false;
202 /// Variables that can be removed from the system once the stack entry gets
203 /// removed.
204 SmallVector<Value *, 2> ValuesToRelease;
205
206 StackEntry(unsigned NumIn, unsigned NumOut, bool IsSigned,
207 SmallVector<Value *, 2> ValuesToRelease)
208 : NumIn(NumIn), NumOut(NumOut), IsSigned(IsSigned),
209 ValuesToRelease(std::move(ValuesToRelease)) {}
210};
211
212struct ConstraintTy {
213 SmallVector<int64_t, 8> Coefficients;
214 SmallVector<ConditionTy, 2> Preconditions;
215
217
218 bool IsSigned = false;
219
220 ConstraintTy() = default;
221
222 ConstraintTy(SmallVector<int64_t, 8> Coefficients, bool IsSigned, bool IsEq,
223 bool IsNe)
224 : Coefficients(std::move(Coefficients)), IsSigned(IsSigned), IsEq(IsEq),
225 IsNe(IsNe) {}
226
227 unsigned size() const { return Coefficients.size(); }
228
229 unsigned empty() const { return Coefficients.empty(); }
230
231 /// Returns true if all preconditions for this list of constraints are
232 /// satisfied given \p Info.
233 bool isValid(const ConstraintInfo &Info) const;
234
235 bool isEq() const { return IsEq; }
236
237 bool isNe() const { return IsNe; }
238
239 /// Check if the current constraint is implied by the given ConstraintSystem.
240 ///
241 /// \return true or false if the constraint is proven to be respectively true,
242 /// or false. When the constraint cannot be proven to be either true or false,
243 /// std::nullopt is returned.
244 std::optional<bool> isImpliedBy(const ConstraintSystem &CS) const;
245
246private:
247 bool IsEq = false;
248 bool IsNe = false;
249};
250
251/// Wrapper encapsulating separate constraint systems and corresponding value
252/// mappings for both unsigned and signed information. Facts are added to and
253/// conditions are checked against the corresponding system depending on the
254/// signed-ness of their predicates. While the information is kept separate
255/// based on signed-ness, certain conditions can be transferred between the two
256/// systems.
257class ConstraintInfo {
258
259 ConstraintSystem UnsignedCS;
260 ConstraintSystem SignedCS;
261
262 const DataLayout &DL;
263
264public:
265 ConstraintInfo(const DataLayout &DL, ArrayRef<Value *> FunctionArgs)
266 : UnsignedCS(FunctionArgs), SignedCS(FunctionArgs), DL(DL) {
267 auto &Value2Index = getValue2Index(false);
268 // Add Arg > -1 constraints to unsigned system for all function arguments.
269 for (Value *Arg : FunctionArgs) {
270 ConstraintTy VarPos(SmallVector<int64_t, 8>(Value2Index.size() + 1, 0),
271 false, false, false);
272 VarPos.Coefficients[Value2Index[Arg]] = -1;
273 UnsignedCS.addVariableRow(VarPos.Coefficients);
274 }
275 }
276
277 DenseMap<Value *, unsigned> &getValue2Index(bool Signed) {
278 return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index();
279 }
280 const DenseMap<Value *, unsigned> &getValue2Index(bool Signed) const {
281 return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index();
282 }
283
284 ConstraintSystem &getCS(bool Signed) {
285 return Signed ? SignedCS : UnsignedCS;
286 }
287 const ConstraintSystem &getCS(bool Signed) const {
288 return Signed ? SignedCS : UnsignedCS;
289 }
290
291 void popLastConstraint(bool Signed) { getCS(Signed).popLastConstraint(); }
292 void popLastNVariables(bool Signed, unsigned N) {
293 getCS(Signed).popLastNVariables(N);
294 }
295
296 bool doesHold(CmpInst::Predicate Pred, Value *A, Value *B) const;
297
298 void addFact(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
299 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack);
300
301 /// Turn a comparison of the form \p Op0 \p Pred \p Op1 into a vector of
302 /// constraints, using indices from the corresponding constraint system.
303 /// New variables that need to be added to the system are collected in
304 /// \p NewVariables.
305 ConstraintTy getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
306 SmallVectorImpl<Value *> &NewVariables,
307 bool ForceSignedSystem = false) const;
308
309 /// Turns a comparison of the form \p Op0 \p Pred \p Op1 into a vector of
310 /// constraints using getConstraint. Returns an empty constraint if the result
311 /// cannot be used to query the existing constraint system, e.g. because it
312 /// would require adding new variables. Also tries to convert signed
313 /// predicates to unsigned ones if possible to allow using the unsigned system
314 /// which increases the effectiveness of the signed <-> unsigned transfer
315 /// logic.
316 ConstraintTy getConstraintForSolving(CmpInst::Predicate Pred, Value *Op0,
317 Value *Op1) const;
318
319 /// Try to add information from \p A \p Pred \p B to the unsigned/signed
320 /// system if \p Pred is signed/unsigned.
321 void transferToOtherSystem(CmpInst::Predicate Pred, Value *A, Value *B,
322 unsigned NumIn, unsigned NumOut,
323 SmallVectorImpl<StackEntry> &DFSInStack);
324
325private:
326 /// Adds facts into constraint system. \p ForceSignedSystem can be set when
327 /// the \p Pred is eq/ne, and signed constraint system is used when it's
328 /// specified.
329 void addFactImpl(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
330 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack,
331 bool ForceSignedSystem);
332};
333
334/// Represents a (Coefficient * Variable) entry after IR decomposition.
335struct DecompEntry {
336 int64_t Coefficient;
337 Value *Variable;
338 /// True if the variable is known positive in the current constraint.
339 bool IsKnownNonNegative;
340
341 DecompEntry(int64_t Coefficient, Value *Variable,
342 bool IsKnownNonNegative = false)
343 : Coefficient(Coefficient), Variable(Variable),
344 IsKnownNonNegative(IsKnownNonNegative) {}
345};
346
347/// Represents an Offset + Coefficient1 * Variable1 + ... decomposition.
348struct Decomposition {
349 int64_t Offset = 0;
351
352 Decomposition(int64_t Offset) : Offset(Offset) {}
353 Decomposition(Value *V, bool IsKnownNonNegative = false) {
354 Vars.emplace_back(1, V, IsKnownNonNegative);
355 }
356 Decomposition(int64_t Offset, ArrayRef<DecompEntry> Vars)
357 : Offset(Offset), Vars(Vars) {}
358
359 /// Add \p OtherOffset and return true if the operation overflows, i.e. the
360 /// new decomposition is invalid.
361 [[nodiscard]] bool add(int64_t OtherOffset) {
362 return AddOverflow(Offset, OtherOffset, Offset);
363 }
364
365 /// Add \p Other and return true if the operation overflows, i.e. the new
366 /// decomposition is invalid.
367 [[nodiscard]] bool add(const Decomposition &Other) {
368 if (add(Other.Offset))
369 return true;
370 append_range(Vars, Other.Vars);
371 return false;
372 }
373
374 /// Subtract \p Other and return true if the operation overflows, i.e. the new
375 /// decomposition is invalid.
376 [[nodiscard]] bool sub(const Decomposition &Other) {
377 Decomposition Tmp = Other;
378 if (Tmp.mul(-1))
379 return true;
380 if (add(Tmp.Offset))
381 return true;
382 append_range(Vars, Tmp.Vars);
383 return false;
384 }
385
386 /// Multiply all coefficients by \p Factor and return true if the operation
387 /// overflows, i.e. the new decomposition is invalid.
388 [[nodiscard]] bool mul(int64_t Factor) {
389 if (MulOverflow(Offset, Factor, Offset))
390 return true;
391 for (auto &Var : Vars)
392 if (MulOverflow(Var.Coefficient, Factor, Var.Coefficient))
393 return true;
394 return false;
395 }
396};
397
398// Variable and constant offsets for a chain of GEPs, with base pointer BasePtr.
399struct OffsetResult {
400 Value *BasePtr;
401 APInt ConstantOffset;
402 SmallMapVector<Value *, APInt, 4> VariableOffsets;
404
405 OffsetResult() : BasePtr(nullptr), ConstantOffset(0, uint64_t(0)) {}
406
408 : BasePtr(GEP.getPointerOperand()), NW(GEP.getNoWrapFlags()) {
409 ConstantOffset = APInt(DL.getIndexTypeSizeInBits(BasePtr->getType()), 0);
410 }
411};
412} // namespace
413
414// Try to collect variable and constant offsets for \p GEP, partly traversing
415// nested GEPs. Returns an OffsetResult with nullptr as BasePtr of collecting
416// the offset fails.
418 OffsetResult Result(GEP, DL);
419 unsigned BitWidth = Result.ConstantOffset.getBitWidth();
420 if (!GEP.collectOffset(DL, BitWidth, Result.VariableOffsets,
421 Result.ConstantOffset))
422 return {};
423
424 // If we have a nested GEP, check if we can combine the constant offset of the
425 // inner GEP with the outer GEP.
426 if (auto *InnerGEP = dyn_cast<GetElementPtrInst>(Result.BasePtr)) {
427 SmallMapVector<Value *, APInt, 4> VariableOffsets2;
428 APInt ConstantOffset2(BitWidth, 0);
429 bool CanCollectInner = InnerGEP->collectOffset(
430 DL, BitWidth, VariableOffsets2, ConstantOffset2);
431 // TODO: Support cases with more than 1 variable offset.
432 if (!CanCollectInner || Result.VariableOffsets.size() > 1 ||
433 VariableOffsets2.size() > 1 ||
434 (Result.VariableOffsets.size() >= 1 && VariableOffsets2.size() >= 1)) {
435 // More than 1 variable index, use outer result.
436 return Result;
437 }
438 Result.BasePtr = InnerGEP->getPointerOperand();
439 Result.ConstantOffset += ConstantOffset2;
440 if (Result.VariableOffsets.size() == 0 && VariableOffsets2.size() == 1)
441 Result.VariableOffsets = VariableOffsets2;
442 Result.NW &= InnerGEP->getNoWrapFlags();
443 }
444 return Result;
445}
446
447static Decomposition decompose(Value *V,
448 SmallVectorImpl<ConditionTy> &Preconditions,
449 bool IsSigned, const DataLayout &DL);
450
451static bool canUseSExt(ConstantInt *CI) {
452 const APInt &Val = CI->getValue();
454}
455
456static Decomposition decomposeGEP(GEPOperator &GEP,
457 SmallVectorImpl<ConditionTy> &Preconditions,
458 bool IsSigned, const DataLayout &DL) {
459 // Do not reason about pointers where the index size is larger than 64 bits,
460 // as the coefficients used to encode constraints are 64 bit integers.
461 if (DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()) > 64)
462 return &GEP;
463
464 assert(!IsSigned && "The logic below only supports decomposition for "
465 "unsigned predicates at the moment.");
466 const auto &[BasePtr, ConstantOffset, VariableOffsets, NW] =
468 // We support either plain gep nuw, or gep nusw with non-negative offset,
469 // which implies gep nuw.
470 if (!BasePtr || NW == GEPNoWrapFlags::none())
471 return &GEP;
472
473 Decomposition Result(ConstantOffset.getSExtValue(), DecompEntry(1, BasePtr));
474 for (auto [Index, Scale] : VariableOffsets) {
475 auto IdxResult = decompose(Index, Preconditions, IsSigned, DL);
476 if (IdxResult.mul(Scale.getSExtValue()))
477 return &GEP;
478 if (Result.add(IdxResult))
479 return &GEP;
480
481 if (!NW.hasNoUnsignedWrap()) {
482 // Try to prove nuw from nusw and nneg.
483 assert(NW.hasNoUnsignedSignedWrap() && "Must have nusw flag");
484 if (!isKnownNonNegative(Index, DL))
485 Preconditions.emplace_back(CmpInst::ICMP_SGE, Index,
486 ConstantInt::get(Index->getType(), 0));
487 }
488 }
489 return Result;
490}
491
492// Decomposes \p V into a constant offset + list of pairs { Coefficient,
493// Variable } where Coefficient * Variable. The sum of the constant offset and
494// pairs equals \p V.
495static Decomposition decompose(Value *V,
496 SmallVectorImpl<ConditionTy> &Preconditions,
497 bool IsSigned, const DataLayout &DL) {
498
499 auto MergeResults = [&Preconditions, IsSigned,
500 &DL](Value *A, Value *B,
501 bool IsSignedB) -> std::optional<Decomposition> {
502 auto ResA = decompose(A, Preconditions, IsSigned, DL);
503 auto ResB = decompose(B, Preconditions, IsSignedB, DL);
504 if (ResA.add(ResB))
505 return std::nullopt;
506 return ResA;
507 };
508
509 Type *Ty = V->getType()->getScalarType();
510 if (Ty->isPointerTy() && !IsSigned) {
511 if (auto *GEP = dyn_cast<GEPOperator>(V))
512 return decomposeGEP(*GEP, Preconditions, IsSigned, DL);
513 if (isa<ConstantPointerNull>(V))
514 return int64_t(0);
515
516 return V;
517 }
518
519 // Don't handle integers > 64 bit. Our coefficients are 64-bit large, so
520 // coefficient add/mul may wrap, while the operation in the full bit width
521 // would not.
522 if (!Ty->isIntegerTy() || Ty->getIntegerBitWidth() > 64)
523 return V;
524
525 bool IsKnownNonNegative = false;
526
527 // Decompose \p V used with a signed predicate.
528 if (IsSigned) {
529 if (auto *CI = dyn_cast<ConstantInt>(V)) {
530 if (canUseSExt(CI))
531 return CI->getSExtValue();
532 }
533 Value *Op0;
534 Value *Op1;
535
536 if (match(V, m_SExt(m_Value(Op0))))
537 V = Op0;
538 else if (match(V, m_NNegZExt(m_Value(Op0)))) {
539 V = Op0;
540 IsKnownNonNegative = true;
541 } else if (match(V, m_NSWTrunc(m_Value(Op0)))) {
542 if (Op0->getType()->getScalarSizeInBits() <= 64)
543 V = Op0;
544 }
545
546 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) {
547 if (auto Decomp = MergeResults(Op0, Op1, IsSigned))
548 return *Decomp;
549 return {V, IsKnownNonNegative};
550 }
551
552 if (match(V, m_NSWSub(m_Value(Op0), m_Value(Op1)))) {
553 auto ResA = decompose(Op0, Preconditions, IsSigned, DL);
554 auto ResB = decompose(Op1, Preconditions, IsSigned, DL);
555 if (!ResA.sub(ResB))
556 return ResA;
557 return {V, IsKnownNonNegative};
558 }
559
560 ConstantInt *CI;
561 if (match(V, m_NSWMul(m_Value(Op0), m_ConstantInt(CI))) && canUseSExt(CI)) {
562 auto Result = decompose(Op0, Preconditions, IsSigned, DL);
563 if (!Result.mul(CI->getSExtValue()))
564 return Result;
565 return {V, IsKnownNonNegative};
566 }
567
568 // (shl nsw x, shift) is (mul nsw x, (1<<shift)), with the exception of
569 // shift == bw-1.
570 if (match(V, m_NSWShl(m_Value(Op0), m_ConstantInt(CI)))) {
571 uint64_t Shift = CI->getValue().getLimitedValue();
572 if (Shift < Ty->getIntegerBitWidth() - 1) {
573 assert(Shift < 64 && "Would overflow");
574 auto Result = decompose(Op0, Preconditions, IsSigned, DL);
575 if (!Result.mul(int64_t(1) << Shift))
576 return Result;
577 return {V, IsKnownNonNegative};
578 }
579 }
580
581 return {V, IsKnownNonNegative};
582 }
583
584 if (auto *CI = dyn_cast<ConstantInt>(V)) {
585 if (CI->uge(MaxConstraintValue))
586 return V;
587 return int64_t(CI->getZExtValue());
588 }
589
590 Value *Op0;
591 if (match(V, m_ZExt(m_Value(Op0)))) {
592 IsKnownNonNegative = true;
593 V = Op0;
594 } else if (match(V, m_SExt(m_Value(Op0)))) {
595 V = Op0;
596 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,
597 ConstantInt::get(Op0->getType(), 0));
598 } else if (auto *Trunc = dyn_cast<TruncInst>(V)) {
599 if (Trunc->getSrcTy()->getScalarSizeInBits() <= 64) {
600 if (Trunc->hasNoUnsignedWrap() || Trunc->hasNoSignedWrap()) {
601 V = Trunc->getOperand(0);
602 if (!Trunc->hasNoUnsignedWrap())
603 Preconditions.emplace_back(CmpInst::ICMP_SGE, V,
604 ConstantInt::get(V->getType(), 0));
605 }
606 }
607 }
608
609 Value *Op1;
610 ConstantInt *CI;
611 if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) {
612 if (auto Decomp = MergeResults(Op0, Op1, IsSigned))
613 return *Decomp;
614 return {V, IsKnownNonNegative};
615 }
616
617 if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) {
618 if (!isKnownNonNegative(Op0, DL))
619 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,
620 ConstantInt::get(Op0->getType(), 0));
621 if (!isKnownNonNegative(Op1, DL))
622 Preconditions.emplace_back(CmpInst::ICMP_SGE, Op1,
623 ConstantInt::get(Op1->getType(), 0));
624
625 if (auto Decomp = MergeResults(Op0, Op1, IsSigned))
626 return *Decomp;
627 return {V, IsKnownNonNegative};
628 }
629
630 if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() &&
631 canUseSExt(CI)) {
632 Preconditions.emplace_back(
634 ConstantInt::get(Op0->getType(), CI->getSExtValue() * -1));
635 if (auto Decomp = MergeResults(Op0, CI, true))
636 return *Decomp;
637 return {V, IsKnownNonNegative};
638 }
639
640 // Decompose or as an add if there are no common bits between the operands.
641 if (match(V, m_DisjointOr(m_Value(Op0), m_ConstantInt(CI)))) {
642 if (auto Decomp = MergeResults(Op0, CI, IsSigned))
643 return *Decomp;
644 return {V, IsKnownNonNegative};
645 }
646
647 if (match(V, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI)) {
648 if (CI->getSExtValue() < 0 || CI->getSExtValue() >= 64)
649 return {V, IsKnownNonNegative};
650 auto Result = decompose(Op1, Preconditions, IsSigned, DL);
651 if (!Result.mul(int64_t{1} << CI->getSExtValue()))
652 return Result;
653 return {V, IsKnownNonNegative};
654 }
655
656 if (match(V, m_NUWMul(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI) &&
657 (!CI->isNegative())) {
658 auto Result = decompose(Op1, Preconditions, IsSigned, DL);
659 if (!Result.mul(CI->getSExtValue()))
660 return Result;
661 return {V, IsKnownNonNegative};
662 }
663
664 if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1)))) {
665 auto ResA = decompose(Op0, Preconditions, IsSigned, DL);
666 auto ResB = decompose(Op1, Preconditions, IsSigned, DL);
667 if (!ResA.sub(ResB))
668 return ResA;
669 return {V, IsKnownNonNegative};
670 }
671
672 return {V, IsKnownNonNegative};
673}
674
675ConstraintTy
676ConstraintInfo::getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
677 SmallVectorImpl<Value *> &NewVariables,
678 bool ForceSignedSystem) const {
679 assert(NewVariables.empty() && "NewVariables must be empty when passed in");
680 assert((!ForceSignedSystem || CmpInst::isEquality(Pred)) &&
681 "signed system can only be forced on eq/ne");
682
683 bool IsEq = false;
684 bool IsNe = false;
685
686 // Try to convert Pred to one of ULE/ULT/SLE/SLT.
687 switch (Pred) {
691 case CmpInst::ICMP_SGE: {
692 Pred = CmpInst::getSwappedPredicate(Pred);
693 std::swap(Op0, Op1);
694 break;
695 }
696 case CmpInst::ICMP_EQ:
697 if (!ForceSignedSystem && match(Op1, m_Zero())) {
698 Pred = CmpInst::ICMP_ULE;
699 } else {
700 IsEq = true;
701 Pred = CmpInst::ICMP_ULE;
702 }
703 break;
704 case CmpInst::ICMP_NE:
705 if (!ForceSignedSystem && match(Op1, m_Zero())) {
707 std::swap(Op0, Op1);
708 } else {
709 IsNe = true;
710 Pred = CmpInst::ICMP_ULE;
711 }
712 break;
713 default:
714 break;
715 }
716
717 if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT &&
718 Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT)
719 return {};
720
721 SmallVector<ConditionTy, 4> Preconditions;
722 bool IsSigned = ForceSignedSystem || CmpInst::isSigned(Pred);
723 auto &Value2Index = getValue2Index(IsSigned);
725 Preconditions, IsSigned, DL);
727 Preconditions, IsSigned, DL);
728 int64_t Offset1 = ADec.Offset;
729 int64_t Offset2 = BDec.Offset;
730 Offset1 *= -1;
731
732 auto &VariablesA = ADec.Vars;
733 auto &VariablesB = BDec.Vars;
734
735 // First try to look up \p V in Value2Index and NewVariables. Otherwise add a
736 // new entry to NewVariables.
738 auto GetOrAddIndex = [&Value2Index, &NewVariables,
739 &NewIndexMap](Value *V) -> unsigned {
740 auto V2I = Value2Index.find(V);
741 if (V2I != Value2Index.end())
742 return V2I->second;
743 auto Insert =
744 NewIndexMap.insert({V, Value2Index.size() + NewVariables.size() + 1});
745 if (Insert.second)
746 NewVariables.push_back(V);
747 return Insert.first->second;
748 };
749
750 // Make sure all variables have entries in Value2Index or NewVariables.
751 for (const auto &KV : concat<DecompEntry>(VariablesA, VariablesB))
752 GetOrAddIndex(KV.Variable);
753
754 // Build result constraint, by first adding all coefficients from A and then
755 // subtracting all coefficients from B.
756 ConstraintTy Res(
757 SmallVector<int64_t, 8>(Value2Index.size() + NewVariables.size() + 1, 0),
758 IsSigned, IsEq, IsNe);
759 // Collect variables that are known to be positive in all uses in the
760 // constraint.
761 SmallDenseMap<Value *, bool> KnownNonNegativeVariables;
762 auto &R = Res.Coefficients;
763 for (const auto &KV : VariablesA) {
764 R[GetOrAddIndex(KV.Variable)] += KV.Coefficient;
765 auto I =
766 KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative});
767 I.first->second &= KV.IsKnownNonNegative;
768 }
769
770 for (const auto &KV : VariablesB) {
771 auto &Coeff = R[GetOrAddIndex(KV.Variable)];
772 if (SubOverflow(Coeff, KV.Coefficient, Coeff))
773 return {};
774 auto I =
775 KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative});
776 I.first->second &= KV.IsKnownNonNegative;
777 }
778
779 int64_t OffsetSum;
780 if (AddOverflow(Offset1, Offset2, OffsetSum))
781 return {};
782 if (Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_ULT)
783 if (AddOverflow(OffsetSum, int64_t(-1), OffsetSum))
784 return {};
785 R[0] = OffsetSum;
786 Res.Preconditions = std::move(Preconditions);
787
788 // Remove any (Coefficient, Variable) entry where the Coefficient is 0 for new
789 // variables.
790 while (!NewVariables.empty()) {
791 int64_t Last = R.back();
792 if (Last != 0)
793 break;
794 R.pop_back();
795 Value *RemovedV = NewVariables.pop_back_val();
796 NewIndexMap.erase(RemovedV);
797 }
798
799 // Add extra constraints for variables that are known positive.
800 for (auto &KV : KnownNonNegativeVariables) {
801 if (!KV.second ||
802 (!Value2Index.contains(KV.first) && !NewIndexMap.contains(KV.first)))
803 continue;
804 auto &C = Res.ExtraInfo.emplace_back(
805 Value2Index.size() + NewVariables.size() + 1, 0);
806 C[GetOrAddIndex(KV.first)] = -1;
807 }
808 return Res;
809}
810
811ConstraintTy ConstraintInfo::getConstraintForSolving(CmpInst::Predicate Pred,
812 Value *Op0,
813 Value *Op1) const {
814 Constant *NullC = Constant::getNullValue(Op0->getType());
815 // Handle trivially true compares directly to avoid adding V UGE 0 constraints
816 // for all variables in the unsigned system.
817 if ((Pred == CmpInst::ICMP_ULE && Op0 == NullC) ||
818 (Pred == CmpInst::ICMP_UGE && Op1 == NullC)) {
819 auto &Value2Index = getValue2Index(false);
820 // Return constraint that's trivially true.
821 return ConstraintTy(SmallVector<int64_t, 8>(Value2Index.size(), 0), false,
822 false, false);
823 }
824
825 // If both operands are known to be non-negative, change signed predicates to
826 // unsigned ones. This increases the reasoning effectiveness in combination
827 // with the signed <-> unsigned transfer logic.
828 if (CmpInst::isSigned(Pred) &&
829 isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1) &&
832
833 SmallVector<Value *> NewVariables;
834 ConstraintTy R = getConstraint(Pred, Op0, Op1, NewVariables);
835 if (!NewVariables.empty())
836 return {};
837 return R;
838}
839
840bool ConstraintTy::isValid(const ConstraintInfo &Info) const {
841 return Coefficients.size() > 0 &&
842 all_of(Preconditions, [&Info](const ConditionTy &C) {
843 return Info.doesHold(C.Pred, C.Op0, C.Op1);
844 });
845}
846
847std::optional<bool>
848ConstraintTy::isImpliedBy(const ConstraintSystem &CS) const {
849 bool IsConditionImplied = CS.isConditionImplied(Coefficients);
850
851 if (IsEq || IsNe) {
852 auto NegatedOrEqual = ConstraintSystem::negateOrEqual(Coefficients);
853 bool IsNegatedOrEqualImplied =
854 !NegatedOrEqual.empty() && CS.isConditionImplied(NegatedOrEqual);
855
856 // In order to check that `%a == %b` is true (equality), both conditions `%a
857 // >= %b` and `%a <= %b` must hold true. When checking for equality (`IsEq`
858 // is true), we return true if they both hold, false in the other cases.
859 if (IsConditionImplied && IsNegatedOrEqualImplied)
860 return IsEq;
861
862 auto Negated = ConstraintSystem::negate(Coefficients);
863 bool IsNegatedImplied = !Negated.empty() && CS.isConditionImplied(Negated);
864
865 auto StrictLessThan = ConstraintSystem::toStrictLessThan(Coefficients);
866 bool IsStrictLessThanImplied =
867 !StrictLessThan.empty() && CS.isConditionImplied(StrictLessThan);
868
869 // In order to check that `%a != %b` is true (non-equality), either
870 // condition `%a > %b` or `%a < %b` must hold true. When checking for
871 // non-equality (`IsNe` is true), we return true if one of the two holds,
872 // false in the other cases.
873 if (IsNegatedImplied || IsStrictLessThanImplied)
874 return IsNe;
875
876 return std::nullopt;
877 }
878
879 if (IsConditionImplied)
880 return true;
881
882 auto Negated = ConstraintSystem::negate(Coefficients);
883 auto IsNegatedImplied = !Negated.empty() && CS.isConditionImplied(Negated);
884 if (IsNegatedImplied)
885 return false;
886
887 // Neither the condition nor its negated holds, did not prove anything.
888 return std::nullopt;
889}
890
891bool ConstraintInfo::doesHold(CmpInst::Predicate Pred, Value *A,
892 Value *B) const {
893 auto R = getConstraintForSolving(Pred, A, B);
894 return R.isValid(*this) &&
895 getCS(R.IsSigned).isConditionImplied(R.Coefficients);
896}
897
898void ConstraintInfo::transferToOtherSystem(
899 CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
900 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack) {
901 auto IsKnownNonNegative = [this](Value *V) {
902 return doesHold(CmpInst::ICMP_SGE, V, ConstantInt::get(V->getType(), 0)) ||
904 };
905 // Check if we can combine facts from the signed and unsigned systems to
906 // derive additional facts.
907 if (!A->getType()->isIntegerTy())
908 return;
909 // FIXME: This currently depends on the order we add facts. Ideally we
910 // would first add all known facts and only then try to add additional
911 // facts.
912 switch (Pred) {
913 default:
914 break;
917 // If B is a signed positive constant, then A >=s 0 and A <s (or <=s) B.
918 if (IsKnownNonNegative(B)) {
919 addFact(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0), NumIn,
920 NumOut, DFSInStack);
921 addFact(ICmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut,
922 DFSInStack);
923 }
924 break;
927 // If A is a signed positive constant, then B >=s 0 and A >s (or >=s) B.
928 if (IsKnownNonNegative(A)) {
929 addFact(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0), NumIn,
930 NumOut, DFSInStack);
931 addFact(ICmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut,
932 DFSInStack);
933 }
934 break;
936 if (IsKnownNonNegative(A))
937 addFact(CmpInst::ICMP_ULT, A, B, NumIn, NumOut, DFSInStack);
938 break;
939 case CmpInst::ICMP_SGT: {
940 if (doesHold(CmpInst::ICMP_SGE, B, Constant::getAllOnesValue(B->getType())))
941 addFact(CmpInst::ICMP_UGE, A, ConstantInt::get(B->getType(), 0), NumIn,
942 NumOut, DFSInStack);
943 if (IsKnownNonNegative(B))
944 addFact(CmpInst::ICMP_UGT, A, B, NumIn, NumOut, DFSInStack);
945
946 break;
947 }
949 if (IsKnownNonNegative(B))
950 addFact(CmpInst::ICMP_UGE, A, B, NumIn, NumOut, DFSInStack);
951 break;
952 }
953}
954
955#ifndef NDEBUG
956
958 const DenseMap<Value *, unsigned> &Value2Index) {
959 ConstraintSystem CS(Value2Index);
961 CS.dump();
962}
963#endif
964
965void State::addInfoForInductions(BasicBlock &BB) {
966 auto *L = LI.getLoopFor(&BB);
967 if (!L || L->getHeader() != &BB)
968 return;
969
970 Value *A;
971 Value *B;
972 CmpPredicate Pred;
973
974 if (!match(BB.getTerminator(),
975 m_Br(m_ICmp(Pred, m_Value(A), m_Value(B)), m_Value(), m_Value())))
976 return;
977 PHINode *PN = dyn_cast<PHINode>(A);
978 if (!PN) {
979 Pred = CmpInst::getSwappedPredicate(Pred);
980 std::swap(A, B);
981 PN = dyn_cast<PHINode>(A);
982 }
983
984 if (!PN || PN->getParent() != &BB || PN->getNumIncomingValues() != 2 ||
985 !SE.isSCEVable(PN->getType()))
986 return;
987
988 BasicBlock *InLoopSucc = nullptr;
989 if (Pred == CmpInst::ICMP_NE)
990 InLoopSucc = cast<BranchInst>(BB.getTerminator())->getSuccessor(0);
991 else if (Pred == CmpInst::ICMP_EQ)
992 InLoopSucc = cast<BranchInst>(BB.getTerminator())->getSuccessor(1);
993 else
994 return;
995
996 if (!L->contains(InLoopSucc) || !L->isLoopExiting(&BB) || InLoopSucc == &BB)
997 return;
998
999 auto *AR = dyn_cast_or_null<SCEVAddRecExpr>(SE.getSCEV(PN));
1000 BasicBlock *LoopPred = L->getLoopPredecessor();
1001 if (!AR || AR->getLoop() != L || !LoopPred)
1002 return;
1003
1004 const SCEV *StartSCEV = AR->getStart();
1005 Value *StartValue = nullptr;
1006 if (auto *C = dyn_cast<SCEVConstant>(StartSCEV)) {
1007 StartValue = C->getValue();
1008 } else {
1009 StartValue = PN->getIncomingValueForBlock(LoopPred);
1010 assert(SE.getSCEV(StartValue) == StartSCEV && "inconsistent start value");
1011 }
1012
1013 DomTreeNode *DTN = DT.getNode(InLoopSucc);
1014 auto IncUnsigned = SE.getMonotonicPredicateType(AR, CmpInst::ICMP_UGT);
1015 auto IncSigned = SE.getMonotonicPredicateType(AR, CmpInst::ICMP_SGT);
1016 bool MonotonicallyIncreasingUnsigned =
1018 bool MonotonicallyIncreasingSigned =
1020 // If SCEV guarantees that AR does not wrap, PN >= StartValue can be added
1021 // unconditionally.
1022 if (MonotonicallyIncreasingUnsigned)
1023 WorkList.push_back(
1024 FactOrCheck::getConditionFact(DTN, CmpInst::ICMP_UGE, PN, StartValue));
1025 if (MonotonicallyIncreasingSigned)
1026 WorkList.push_back(
1027 FactOrCheck::getConditionFact(DTN, CmpInst::ICMP_SGE, PN, StartValue));
1028
1029 APInt StepOffset;
1030 if (auto *C = dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE)))
1031 StepOffset = C->getAPInt();
1032 else
1033 return;
1034
1035 // Make sure the bound B is loop-invariant.
1036 if (!L->isLoopInvariant(B))
1037 return;
1038
1039 // Handle negative steps.
1040 if (StepOffset.isNegative()) {
1041 // TODO: Extend to allow steps > -1.
1042 if (!(-StepOffset).isOne())
1043 return;
1044
1045 // AR may wrap.
1046 // Add StartValue >= PN conditional on B <= StartValue which guarantees that
1047 // the loop exits before wrapping with a step of -1.
1048 WorkList.push_back(FactOrCheck::getConditionFact(
1049 DTN, CmpInst::ICMP_UGE, StartValue, PN,
1050 ConditionTy(CmpInst::ICMP_ULE, B, StartValue)));
1051 WorkList.push_back(FactOrCheck::getConditionFact(
1052 DTN, CmpInst::ICMP_SGE, StartValue, PN,
1053 ConditionTy(CmpInst::ICMP_SLE, B, StartValue)));
1054 // Add PN > B conditional on B <= StartValue which guarantees that the loop
1055 // exits when reaching B with a step of -1.
1056 WorkList.push_back(FactOrCheck::getConditionFact(
1057 DTN, CmpInst::ICMP_UGT, PN, B,
1058 ConditionTy(CmpInst::ICMP_ULE, B, StartValue)));
1059 WorkList.push_back(FactOrCheck::getConditionFact(
1060 DTN, CmpInst::ICMP_SGT, PN, B,
1061 ConditionTy(CmpInst::ICMP_SLE, B, StartValue)));
1062 return;
1063 }
1064
1065 // Make sure AR either steps by 1 or that the value we compare against is a
1066 // GEP based on the same start value and all offsets are a multiple of the
1067 // step size, to guarantee that the induction will reach the value.
1068 if (StepOffset.isZero() || StepOffset.isNegative())
1069 return;
1070
1071 if (!StepOffset.isOne()) {
1072 // Check whether B-Start is known to be a multiple of StepOffset.
1073 const SCEV *BMinusStart = SE.getMinusSCEV(SE.getSCEV(B), StartSCEV);
1074 if (isa<SCEVCouldNotCompute>(BMinusStart) ||
1075 !SE.getConstantMultiple(BMinusStart).urem(StepOffset).isZero())
1076 return;
1077 }
1078
1079 // AR may wrap. Add PN >= StartValue conditional on StartValue <= B which
1080 // guarantees that the loop exits before wrapping in combination with the
1081 // restrictions on B and the step above.
1082 if (!MonotonicallyIncreasingUnsigned)
1083 WorkList.push_back(FactOrCheck::getConditionFact(
1084 DTN, CmpInst::ICMP_UGE, PN, StartValue,
1085 ConditionTy(CmpInst::ICMP_ULE, StartValue, B)));
1086 if (!MonotonicallyIncreasingSigned)
1087 WorkList.push_back(FactOrCheck::getConditionFact(
1088 DTN, CmpInst::ICMP_SGE, PN, StartValue,
1089 ConditionTy(CmpInst::ICMP_SLE, StartValue, B)));
1090
1091 WorkList.push_back(FactOrCheck::getConditionFact(
1092 DTN, CmpInst::ICMP_ULT, PN, B,
1093 ConditionTy(CmpInst::ICMP_ULE, StartValue, B)));
1094 WorkList.push_back(FactOrCheck::getConditionFact(
1095 DTN, CmpInst::ICMP_SLT, PN, B,
1096 ConditionTy(CmpInst::ICMP_SLE, StartValue, B)));
1097
1098 // Try to add condition from header to the dedicated exit blocks. When exiting
1099 // either with EQ or NE in the header, we know that the induction value must
1100 // be u<= B, as other exits may only exit earlier.
1101 assert(!StepOffset.isNegative() && "induction must be increasing");
1102 assert((Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) &&
1103 "unsupported predicate");
1104 ConditionTy Precond = {CmpInst::ICMP_ULE, StartValue, B};
1106 L->getExitBlocks(ExitBBs);
1107 for (BasicBlock *EB : ExitBBs) {
1108 // Bail out on non-dedicated exits.
1109 if (DT.dominates(&BB, EB)) {
1110 WorkList.emplace_back(FactOrCheck::getConditionFact(
1111 DT.getNode(EB), CmpInst::ICMP_ULE, A, B, Precond));
1112 }
1113 }
1114}
1115
1117 uint64_t AccessSize,
1118 CmpPredicate &Pred, Value *&A,
1119 Value *&B, const DataLayout &DL,
1120 const TargetLibraryInfo &TLI) {
1121 auto Offset = collectOffsets(cast<GEPOperator>(GEP), DL);
1122 if (!Offset.NW.hasNoUnsignedWrap())
1123 return false;
1124
1125 if (Offset.VariableOffsets.size() != 1)
1126 return false;
1127
1128 ObjectSizeOpts Opts;
1129 // Workaround for gep inbounds, ptr null, idx.
1130 Opts.NullIsUnknownSize = true;
1131 // Be conservative since we are not clear on whether an out of bounds access
1132 // to the padding is UB or not.
1133 Opts.RoundToAlign = true;
1134 std::optional<TypeSize> Size =
1135 getBaseObjectSize(Offset.BasePtr, DL, &TLI, Opts);
1136 if (!Size || Size->isScalable())
1137 return false;
1138
1139 // Index * Scale + ConstOffset + AccessSize <= AllocSize
1140 // With nuw flag, we know that the index addition doesn't have unsigned wrap.
1141 // If (AllocSize - (ConstOffset + AccessSize)) wraps around, there is no valid
1142 // value for Index.
1143 uint64_t BitWidth = Offset.ConstantOffset.getBitWidth();
1144 auto &[Index, Scale] = Offset.VariableOffsets.front();
1145 APInt MaxIndex = (APInt(BitWidth, Size->getFixedValue() - AccessSize,
1146 /*isSigned=*/false, /*implicitTrunc=*/true) -
1147 Offset.ConstantOffset)
1148 .udiv(Scale);
1149 Pred = ICmpInst::ICMP_ULE;
1150 A = Index;
1151 B = ConstantInt::get(Index->getType(), MaxIndex);
1152 return true;
1153}
1154
1155void State::addInfoFor(BasicBlock &BB) {
1156 addInfoForInductions(BB);
1157 auto &DL = BB.getDataLayout();
1158
1159 // True as long as the current instruction is guaranteed to execute.
1160 bool GuaranteedToExecute = true;
1161 // Queue conditions and assumes.
1162 for (Instruction &I : BB) {
1163 if (auto *Cmp = dyn_cast<ICmpInst>(&I)) {
1164 for (Use &U : Cmp->uses()) {
1165 auto *UserI = getContextInstForUse(U);
1166 auto *DTN = DT.getNode(UserI->getParent());
1167 if (!DTN)
1168 continue;
1169 WorkList.push_back(FactOrCheck::getCheck(DTN, &U));
1170 }
1171 continue;
1172 }
1173
1174 auto AddFactFromMemoryAccess = [&](Value *Ptr, Type *AccessType) {
1175 auto *GEP = dyn_cast<GetElementPtrInst>(Ptr);
1176 if (!GEP)
1177 return;
1178 TypeSize AccessSize = DL.getTypeStoreSize(AccessType);
1179 if (!AccessSize.isFixed())
1180 return;
1181 if (GuaranteedToExecute) {
1182 CmpPredicate Pred;
1183 Value *A, *B;
1185 Pred, A, B, DL, TLI)) {
1186 // The memory access is guaranteed to execute when BB is entered,
1187 // hence the constraint holds on entry to BB.
1188 WorkList.emplace_back(FactOrCheck::getConditionFact(
1189 DT.getNode(I.getParent()), Pred, A, B));
1190 }
1191 } else {
1192 WorkList.emplace_back(
1193 FactOrCheck::getInstFact(DT.getNode(I.getParent()), &I));
1194 }
1195 };
1196
1197 if (auto *LI = dyn_cast<LoadInst>(&I)) {
1198 if (!LI->isVolatile())
1199 AddFactFromMemoryAccess(LI->getPointerOperand(), LI->getAccessType());
1200 }
1201 if (auto *SI = dyn_cast<StoreInst>(&I)) {
1202 if (!SI->isVolatile())
1203 AddFactFromMemoryAccess(SI->getPointerOperand(), SI->getAccessType());
1204 }
1205
1206 auto *II = dyn_cast<IntrinsicInst>(&I);
1207 Intrinsic::ID ID = II ? II->getIntrinsicID() : Intrinsic::not_intrinsic;
1208 switch (ID) {
1209 case Intrinsic::assume: {
1210 Value *A, *B;
1211 CmpPredicate Pred;
1212 if (!match(I.getOperand(0), m_ICmp(Pred, m_Value(A), m_Value(B))))
1213 break;
1214 if (GuaranteedToExecute) {
1215 // The assume is guaranteed to execute when BB is entered, hence Cond
1216 // holds on entry to BB.
1217 WorkList.emplace_back(FactOrCheck::getConditionFact(
1218 DT.getNode(I.getParent()), Pred, A, B));
1219 } else {
1220 WorkList.emplace_back(
1221 FactOrCheck::getInstFact(DT.getNode(I.getParent()), &I));
1222 }
1223 break;
1224 }
1225 // Enqueue ssub_with_overflow for simplification.
1226 case Intrinsic::ssub_with_overflow:
1227 case Intrinsic::ucmp:
1228 case Intrinsic::scmp:
1229 WorkList.push_back(
1230 FactOrCheck::getCheck(DT.getNode(&BB), cast<CallInst>(&I)));
1231 break;
1232 // Enqueue the intrinsics to add extra info.
1233 case Intrinsic::umin:
1234 case Intrinsic::umax:
1235 case Intrinsic::smin:
1236 case Intrinsic::smax:
1237 // TODO: handle llvm.abs as well
1238 WorkList.push_back(
1239 FactOrCheck::getCheck(DT.getNode(&BB), cast<CallInst>(&I)));
1240 [[fallthrough]];
1241 case Intrinsic::uadd_sat:
1242 case Intrinsic::usub_sat:
1243 // TODO: Check if it is possible to instead only added the min/max facts
1244 // when simplifying uses of the min/max intrinsics.
1246 break;
1247 [[fallthrough]];
1248 case Intrinsic::abs:
1249 WorkList.push_back(FactOrCheck::getInstFact(DT.getNode(&BB), &I));
1250 break;
1251 }
1252
1253 GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I);
1254 }
1255
1256 if (auto *Switch = dyn_cast<SwitchInst>(BB.getTerminator())) {
1257 for (auto &Case : Switch->cases()) {
1258 BasicBlock *Succ = Case.getCaseSuccessor();
1259 Value *V = Case.getCaseValue();
1260 if (!canAddSuccessor(BB, Succ))
1261 continue;
1262 WorkList.emplace_back(FactOrCheck::getConditionFact(
1263 DT.getNode(Succ), CmpInst::ICMP_EQ, Switch->getCondition(), V));
1264 }
1265 return;
1266 }
1267
1268 auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
1269 if (!Br || !Br->isConditional())
1270 return;
1271
1272 Value *Cond = Br->getCondition();
1273
1274 // If the condition is a chain of ORs/AND and the successor only has the
1275 // current block as predecessor, queue conditions for the successor.
1276 Value *Op0, *Op1;
1277 if (match(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1))) ||
1278 match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
1279 bool IsOr = match(Cond, m_LogicalOr());
1280 bool IsAnd = match(Cond, m_LogicalAnd());
1281 // If there's a select that matches both AND and OR, we need to commit to
1282 // one of the options. Arbitrarily pick OR.
1283 if (IsOr && IsAnd)
1284 IsAnd = false;
1285
1286 BasicBlock *Successor = Br->getSuccessor(IsOr ? 1 : 0);
1287 if (canAddSuccessor(BB, Successor)) {
1288 SmallVector<Value *> CondWorkList;
1289 SmallPtrSet<Value *, 8> SeenCond;
1290 auto QueueValue = [&CondWorkList, &SeenCond](Value *V) {
1291 if (SeenCond.insert(V).second)
1292 CondWorkList.push_back(V);
1293 };
1294 QueueValue(Op1);
1295 QueueValue(Op0);
1296 while (!CondWorkList.empty()) {
1297 Value *Cur = CondWorkList.pop_back_val();
1298 if (auto *Cmp = dyn_cast<ICmpInst>(Cur)) {
1299 WorkList.emplace_back(FactOrCheck::getConditionFact(
1300 DT.getNode(Successor),
1301 IsOr ? Cmp->getInverseCmpPredicate() : Cmp->getCmpPredicate(),
1302 Cmp->getOperand(0), Cmp->getOperand(1)));
1303 continue;
1304 }
1305 if (IsOr && match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) {
1306 QueueValue(Op1);
1307 QueueValue(Op0);
1308 continue;
1309 }
1310 if (IsAnd && match(Cur, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
1311 QueueValue(Op1);
1312 QueueValue(Op0);
1313 continue;
1314 }
1315 }
1316 }
1317 return;
1318 }
1319
1320 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
1321 if (!CmpI)
1322 return;
1323 if (canAddSuccessor(BB, Br->getSuccessor(0)))
1324 WorkList.emplace_back(FactOrCheck::getConditionFact(
1325 DT.getNode(Br->getSuccessor(0)), CmpI->getCmpPredicate(),
1326 CmpI->getOperand(0), CmpI->getOperand(1)));
1327 if (canAddSuccessor(BB, Br->getSuccessor(1)))
1328 WorkList.emplace_back(FactOrCheck::getConditionFact(
1329 DT.getNode(Br->getSuccessor(1)), CmpI->getInverseCmpPredicate(),
1330 CmpI->getOperand(0), CmpI->getOperand(1)));
1331}
1332
1333#ifndef NDEBUG
1335 Value *LHS, Value *RHS) {
1336 OS << "icmp " << Pred << ' ';
1337 LHS->printAsOperand(OS, /*PrintType=*/true);
1338 OS << ", ";
1339 RHS->printAsOperand(OS, /*PrintType=*/false);
1340}
1341#endif
1342
1343namespace {
1344/// Helper to keep track of a condition and if it should be treated as negated
1345/// for reproducer construction.
1346/// Pred == Predicate::BAD_ICMP_PREDICATE indicates that this entry is a
1347/// placeholder to keep the ReproducerCondStack in sync with DFSInStack.
1348struct ReproducerEntry {
1350 Value *LHS;
1351 Value *RHS;
1352
1353 ReproducerEntry(ICmpInst::Predicate Pred, Value *LHS, Value *RHS)
1354 : Pred(Pred), LHS(LHS), RHS(RHS) {}
1355};
1356} // namespace
1357
1358/// Helper function to generate a reproducer function for simplifying \p Cond.
1359/// The reproducer function contains a series of @llvm.assume calls, one for
1360/// each condition in \p Stack. For each condition, the operand instruction are
1361/// cloned until we reach operands that have an entry in \p Value2Index. Those
1362/// will then be added as function arguments. \p DT is used to order cloned
1363/// instructions. The reproducer function will get added to \p M, if it is
1364/// non-null. Otherwise no reproducer function is generated.
1367 ConstraintInfo &Info, DominatorTree &DT) {
1368 if (!M)
1369 return;
1370
1371 LLVMContext &Ctx = Cond->getContext();
1372
1373 LLVM_DEBUG(dbgs() << "Creating reproducer for " << *Cond << "\n");
1374
1375 ValueToValueMapTy Old2New;
1378 // Traverse Cond and its operands recursively until we reach a value that's in
1379 // Value2Index or not an instruction, or not a operation that
1380 // ConstraintElimination can decompose. Such values will be considered as
1381 // external inputs to the reproducer, they are collected and added as function
1382 // arguments later.
1383 auto CollectArguments = [&](ArrayRef<Value *> Ops, bool IsSigned) {
1384 auto &Value2Index = Info.getValue2Index(IsSigned);
1385 SmallVector<Value *, 4> WorkList(Ops);
1386 while (!WorkList.empty()) {
1387 Value *V = WorkList.pop_back_val();
1388 if (!Seen.insert(V).second)
1389 continue;
1390 if (Old2New.find(V) != Old2New.end())
1391 continue;
1392 if (isa<Constant>(V))
1393 continue;
1394
1395 auto *I = dyn_cast<Instruction>(V);
1396 if (Value2Index.contains(V) || !I ||
1397 !isa<CmpInst, BinaryOperator, GEPOperator, CastInst>(V)) {
1398 Old2New[V] = V;
1399 Args.push_back(V);
1400 LLVM_DEBUG(dbgs() << " found external input " << *V << "\n");
1401 } else {
1402 append_range(WorkList, I->operands());
1403 }
1404 }
1405 };
1406
1407 for (auto &Entry : Stack)
1408 if (Entry.Pred != ICmpInst::BAD_ICMP_PREDICATE)
1409 CollectArguments({Entry.LHS, Entry.RHS}, ICmpInst::isSigned(Entry.Pred));
1410 CollectArguments(Cond, ICmpInst::isSigned(Cond->getPredicate()));
1411
1412 SmallVector<Type *> ParamTys;
1413 for (auto *P : Args)
1414 ParamTys.push_back(P->getType());
1415
1416 FunctionType *FTy = FunctionType::get(Cond->getType(), ParamTys,
1417 /*isVarArg=*/false);
1418 Function *F = Function::Create(FTy, Function::ExternalLinkage,
1419 Cond->getModule()->getName() +
1420 Cond->getFunction()->getName() + "repro",
1421 M);
1422 // Add arguments to the reproducer function for each external value collected.
1423 for (unsigned I = 0; I < Args.size(); ++I) {
1424 F->getArg(I)->setName(Args[I]->getName());
1425 Old2New[Args[I]] = F->getArg(I);
1426 }
1427
1428 BasicBlock *Entry = BasicBlock::Create(Ctx, "entry", F);
1429 IRBuilder<> Builder(Entry);
1430 Builder.CreateRet(Builder.getTrue());
1431 Builder.SetInsertPoint(Entry->getTerminator());
1432
1433 // Clone instructions in \p Ops and their operands recursively until reaching
1434 // an value in Value2Index (external input to the reproducer). Update Old2New
1435 // mapping for the original and cloned instructions. Sort instructions to
1436 // clone by dominance, then insert the cloned instructions in the function.
1437 auto CloneInstructions = [&](ArrayRef<Value *> Ops, bool IsSigned) {
1438 SmallVector<Value *, 4> WorkList(Ops);
1440 auto &Value2Index = Info.getValue2Index(IsSigned);
1441 while (!WorkList.empty()) {
1442 Value *V = WorkList.pop_back_val();
1443 if (Old2New.find(V) != Old2New.end())
1444 continue;
1445
1446 auto *I = dyn_cast<Instruction>(V);
1447 if (!Value2Index.contains(V) && I) {
1448 Old2New[V] = nullptr;
1449 ToClone.push_back(I);
1450 append_range(WorkList, I->operands());
1451 }
1452 }
1453
1454 sort(ToClone,
1455 [&DT](Instruction *A, Instruction *B) { return DT.dominates(A, B); });
1456 for (Instruction *I : ToClone) {
1457 Instruction *Cloned = I->clone();
1458 Old2New[I] = Cloned;
1459 Old2New[I]->setName(I->getName());
1460 Cloned->insertBefore(Builder.GetInsertPoint());
1462 Cloned->setDebugLoc({});
1463 }
1464 };
1465
1466 // Materialize the assumptions for the reproducer using the entries in Stack.
1467 // That is, first clone the operands of the condition recursively until we
1468 // reach an external input to the reproducer and add them to the reproducer
1469 // function. Then add an ICmp for the condition (with the inverse predicate if
1470 // the entry is negated) and an assert using the ICmp.
1471 for (auto &Entry : Stack) {
1472 if (Entry.Pred == ICmpInst::BAD_ICMP_PREDICATE)
1473 continue;
1474
1475 LLVM_DEBUG(dbgs() << " Materializing assumption ";
1476 dumpUnpackedICmp(dbgs(), Entry.Pred, Entry.LHS, Entry.RHS);
1477 dbgs() << "\n");
1478 CloneInstructions({Entry.LHS, Entry.RHS}, CmpInst::isSigned(Entry.Pred));
1479
1480 auto *Cmp = Builder.CreateICmp(Entry.Pred, Entry.LHS, Entry.RHS);
1481 Builder.CreateAssumption(Cmp);
1482 }
1483
1484 // Finally, clone the condition to reproduce and remap instruction operands in
1485 // the reproducer using Old2New.
1486 CloneInstructions(Cond, CmpInst::isSigned(Cond->getPredicate()));
1487 Entry->getTerminator()->setOperand(0, Cond);
1488 remapInstructionsInBlocks({Entry}, Old2New);
1489
1490 assert(!verifyFunction(*F, &dbgs()));
1491}
1492
1493static std::optional<bool> checkCondition(CmpInst::Predicate Pred, Value *A,
1494 Value *B, Instruction *CheckInst,
1495 ConstraintInfo &Info) {
1496 LLVM_DEBUG(dbgs() << "Checking " << *CheckInst << "\n");
1497
1498 auto R = Info.getConstraintForSolving(Pred, A, B);
1499 if (R.empty() || !R.isValid(Info)) {
1500 LLVM_DEBUG(dbgs() << " failed to decompose condition\n");
1501 return std::nullopt;
1502 }
1503
1504 auto &CSToUse = Info.getCS(R.IsSigned);
1505
1506 // If there was extra information collected during decomposition, apply
1507 // it now and remove it immediately once we are done with reasoning
1508 // about the constraint.
1509 for (auto &Row : R.ExtraInfo)
1510 CSToUse.addVariableRow(Row);
1511 auto InfoRestorer = make_scope_exit([&]() {
1512 for (unsigned I = 0; I < R.ExtraInfo.size(); ++I)
1513 CSToUse.popLastConstraint();
1514 });
1515
1516 if (auto ImpliedCondition = R.isImpliedBy(CSToUse)) {
1517 if (!DebugCounter::shouldExecute(EliminatedCounter))
1518 return std::nullopt;
1519
1520 LLVM_DEBUG({
1521 dbgs() << "Condition ";
1523 dbgs(), *ImpliedCondition ? Pred : CmpInst::getInversePredicate(Pred),
1524 A, B);
1525 dbgs() << " implied by dominating constraints\n";
1526 CSToUse.dump();
1527 });
1528 return ImpliedCondition;
1529 }
1530
1531 return std::nullopt;
1532}
1533
1535 ICmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut,
1536 Instruction *ContextInst, Module *ReproducerModule,
1537 ArrayRef<ReproducerEntry> ReproducerCondStack, DominatorTree &DT,
1539 auto ReplaceCmpWithConstant = [&](CmpInst *Cmp, bool IsTrue) {
1540 generateReproducer(Cmp, ReproducerModule, ReproducerCondStack, Info, DT);
1541 Constant *ConstantC = ConstantInt::getBool(
1542 CmpInst::makeCmpResultType(Cmp->getType()), IsTrue);
1543 bool Changed = false;
1544 Cmp->replaceUsesWithIf(ConstantC, [&DT, NumIn, NumOut, ContextInst,
1545 &Changed](Use &U) {
1546 auto *UserI = getContextInstForUse(U);
1547 auto *DTN = DT.getNode(UserI->getParent());
1548 if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut)
1549 return false;
1550 if (UserI->getParent() == ContextInst->getParent() &&
1551 UserI->comesBefore(ContextInst))
1552 return false;
1553
1554 // Conditions in an assume trivially simplify to true. Skip uses
1555 // in assume calls to not destroy the available information.
1556 auto *II = dyn_cast<IntrinsicInst>(U.getUser());
1557 bool ShouldReplace = !II || II->getIntrinsicID() != Intrinsic::assume;
1558 Changed |= ShouldReplace;
1559 return ShouldReplace;
1560 });
1561 NumCondsRemoved++;
1562
1563 // Update the debug value records that satisfy the same condition used
1564 // in replaceUsesWithIf.
1566 findDbgUsers(Cmp, DVRUsers);
1567
1568 for (auto *DVR : DVRUsers) {
1569 auto *DTN = DT.getNode(DVR->getParent());
1570 if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut)
1571 continue;
1572
1573 auto *MarkedI = DVR->getInstruction();
1574 if (MarkedI->getParent() == ContextInst->getParent() &&
1575 MarkedI->comesBefore(ContextInst))
1576 continue;
1577
1578 DVR->replaceVariableLocationOp(Cmp, ConstantC);
1579 }
1580
1581 if (Cmp->use_empty())
1582 ToRemove.push_back(Cmp);
1583
1584 return Changed;
1585 };
1586
1587 if (auto ImpliedCondition =
1588 checkCondition(Cmp->getPredicate(), Cmp->getOperand(0),
1589 Cmp->getOperand(1), Cmp, Info))
1590 return ReplaceCmpWithConstant(Cmp, *ImpliedCondition);
1591
1592 // When the predicate is samesign and unsigned, we can also make use of the
1593 // signed predicate information.
1594 if (Cmp->hasSameSign() && Cmp->isUnsigned())
1595 if (auto ImpliedCondition =
1596 checkCondition(Cmp->getSignedPredicate(), Cmp->getOperand(0),
1597 Cmp->getOperand(1), Cmp, Info))
1598 return ReplaceCmpWithConstant(Cmp, *ImpliedCondition);
1599
1600 return false;
1601}
1602
1603static bool checkAndReplaceMinMax(MinMaxIntrinsic *MinMax, ConstraintInfo &Info,
1605 auto ReplaceMinMaxWithOperand = [&](MinMaxIntrinsic *MinMax, bool UseLHS) {
1606 // TODO: generate reproducer for min/max.
1607 MinMax->replaceAllUsesWith(MinMax->getOperand(UseLHS ? 0 : 1));
1608 ToRemove.push_back(MinMax);
1609 return true;
1610 };
1611
1612 ICmpInst::Predicate Pred =
1613 ICmpInst::getNonStrictPredicate(MinMax->getPredicate());
1614 if (auto ImpliedCondition = checkCondition(
1615 Pred, MinMax->getOperand(0), MinMax->getOperand(1), MinMax, Info))
1616 return ReplaceMinMaxWithOperand(MinMax, *ImpliedCondition);
1617 if (auto ImpliedCondition = checkCondition(
1618 Pred, MinMax->getOperand(1), MinMax->getOperand(0), MinMax, Info))
1619 return ReplaceMinMaxWithOperand(MinMax, !*ImpliedCondition);
1620 return false;
1621}
1622
1623static bool checkAndReplaceCmp(CmpIntrinsic *I, ConstraintInfo &Info,
1625 Value *LHS = I->getOperand(0);
1626 Value *RHS = I->getOperand(1);
1627 if (checkCondition(I->getGTPredicate(), LHS, RHS, I, Info).value_or(false)) {
1628 I->replaceAllUsesWith(ConstantInt::get(I->getType(), 1));
1629 ToRemove.push_back(I);
1630 return true;
1631 }
1632 if (checkCondition(I->getLTPredicate(), LHS, RHS, I, Info).value_or(false)) {
1633 I->replaceAllUsesWith(ConstantInt::getSigned(I->getType(), -1));
1634 ToRemove.push_back(I);
1635 return true;
1636 }
1637 if (checkCondition(ICmpInst::ICMP_EQ, LHS, RHS, I, Info).value_or(false)) {
1638 I->replaceAllUsesWith(ConstantInt::get(I->getType(), 0));
1639 ToRemove.push_back(I);
1640 return true;
1641 }
1642 return false;
1643}
1644
1645static void
1646removeEntryFromStack(const StackEntry &E, ConstraintInfo &Info,
1647 Module *ReproducerModule,
1648 SmallVectorImpl<ReproducerEntry> &ReproducerCondStack,
1649 SmallVectorImpl<StackEntry> &DFSInStack) {
1650 Info.popLastConstraint(E.IsSigned);
1651 // Remove variables in the system that went out of scope.
1652 auto &Mapping = Info.getValue2Index(E.IsSigned);
1653 for (Value *V : E.ValuesToRelease)
1654 Mapping.erase(V);
1655 Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());
1656 DFSInStack.pop_back();
1657 if (ReproducerModule)
1658 ReproducerCondStack.pop_back();
1659}
1660
1661/// Check if either the first condition of an AND or OR is implied by the
1662/// (negated in case of OR) second condition or vice versa.
1664 FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule,
1665 SmallVectorImpl<ReproducerEntry> &ReproducerCondStack,
1666 SmallVectorImpl<StackEntry> &DFSInStack,
1668 Instruction *JoinOp = CB.getContextInst();
1669 if (JoinOp->use_empty())
1670 return false;
1671
1672 CmpInst *CmpToCheck = cast<CmpInst>(CB.getInstructionToSimplify());
1673 unsigned OtherOpIdx = JoinOp->getOperand(0) == CmpToCheck ? 1 : 0;
1674
1675 // Don't try to simplify the first condition of a select by the second, as
1676 // this may make the select more poisonous than the original one.
1677 // TODO: check if the first operand may be poison.
1678 if (OtherOpIdx != 0 && isa<SelectInst>(JoinOp))
1679 return false;
1680
1681 unsigned OldSize = DFSInStack.size();
1682 auto InfoRestorer = make_scope_exit([&]() {
1683 // Remove entries again.
1684 while (OldSize < DFSInStack.size()) {
1685 StackEntry E = DFSInStack.back();
1686 removeEntryFromStack(E, Info, ReproducerModule, ReproducerCondStack,
1687 DFSInStack);
1688 }
1689 });
1690 bool IsOr = match(JoinOp, m_LogicalOr());
1691 SmallVector<Value *, 4> Worklist({JoinOp->getOperand(OtherOpIdx)});
1692 // Do a traversal of the AND/OR tree to add facts from leaf compares.
1693 while (!Worklist.empty()) {
1694 Value *Val = Worklist.pop_back_val();
1695 Value *LHS, *RHS;
1696 CmpPredicate Pred;
1697 if (match(Val, m_ICmp(Pred, m_Value(LHS), m_Value(RHS)))) {
1698 // For OR, check if the negated condition implies CmpToCheck.
1699 if (IsOr)
1700 Pred = CmpInst::getInversePredicate(Pred);
1701 // Optimistically add fact from the other compares in the AND/OR.
1702 Info.addFact(Pred, LHS, RHS, CB.NumIn, CB.NumOut, DFSInStack);
1703 continue;
1704 }
1705 if (IsOr ? match(Val, m_LogicalOr(m_Value(LHS), m_Value(RHS)))
1706 : match(Val, m_LogicalAnd(m_Value(LHS), m_Value(RHS)))) {
1707 Worklist.push_back(LHS);
1708 Worklist.push_back(RHS);
1709 }
1710 }
1711 if (OldSize == DFSInStack.size())
1712 return false;
1713
1714 // Check if the second condition can be simplified now.
1715 if (auto ImpliedCondition =
1716 checkCondition(CmpToCheck->getPredicate(), CmpToCheck->getOperand(0),
1717 CmpToCheck->getOperand(1), CmpToCheck, Info)) {
1718 if (IsOr == *ImpliedCondition)
1719 JoinOp->replaceAllUsesWith(
1720 ConstantInt::getBool(JoinOp->getType(), *ImpliedCondition));
1721 else
1722 JoinOp->replaceAllUsesWith(JoinOp->getOperand(OtherOpIdx));
1723 ToRemove.push_back(JoinOp);
1724 return true;
1725 }
1726
1727 return false;
1728}
1729
1730void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B,
1731 unsigned NumIn, unsigned NumOut,
1732 SmallVectorImpl<StackEntry> &DFSInStack) {
1733 addFactImpl(Pred, A, B, NumIn, NumOut, DFSInStack, false);
1734 // If the Pred is eq/ne, also add the fact to signed system.
1735 if (CmpInst::isEquality(Pred))
1736 addFactImpl(Pred, A, B, NumIn, NumOut, DFSInStack, true);
1737}
1738
1739void ConstraintInfo::addFactImpl(CmpInst::Predicate Pred, Value *A, Value *B,
1740 unsigned NumIn, unsigned NumOut,
1741 SmallVectorImpl<StackEntry> &DFSInStack,
1742 bool ForceSignedSystem) {
1743 // If the constraint has a pre-condition, skip the constraint if it does not
1744 // hold.
1745 SmallVector<Value *> NewVariables;
1746 auto R = getConstraint(Pred, A, B, NewVariables, ForceSignedSystem);
1747
1748 // TODO: Support non-equality for facts as well.
1749 if (!R.isValid(*this) || R.isNe())
1750 return;
1751
1752 LLVM_DEBUG(dbgs() << "Adding '"; dumpUnpackedICmp(dbgs(), Pred, A, B);
1753 dbgs() << "'\n");
1754 auto &CSToUse = getCS(R.IsSigned);
1755 if (R.Coefficients.empty())
1756 return;
1757
1758 bool Added = CSToUse.addVariableRowFill(R.Coefficients);
1759 if (!Added)
1760 return;
1761
1762 // If R has been added to the system, add the new variables and queue it for
1763 // removal once it goes out-of-scope.
1764 SmallVector<Value *, 2> ValuesToRelease;
1765 auto &Value2Index = getValue2Index(R.IsSigned);
1766 for (Value *V : NewVariables) {
1767 Value2Index.insert({V, Value2Index.size() + 1});
1768 ValuesToRelease.push_back(V);
1769 }
1770
1771 LLVM_DEBUG({
1772 dbgs() << " constraint: ";
1773 dumpConstraint(R.Coefficients, getValue2Index(R.IsSigned));
1774 dbgs() << "\n";
1775 });
1776
1777 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
1778 std::move(ValuesToRelease));
1779
1780 if (!R.IsSigned) {
1781 for (Value *V : NewVariables) {
1782 ConstraintTy VarPos(SmallVector<int64_t, 8>(Value2Index.size() + 1, 0),
1783 false, false, false);
1784 VarPos.Coefficients[Value2Index[V]] = -1;
1785 CSToUse.addVariableRow(VarPos.Coefficients);
1786 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
1788 }
1789 }
1790
1791 if (R.isEq()) {
1792 // Also add the inverted constraint for equality constraints.
1793 for (auto &Coeff : R.Coefficients)
1794 Coeff *= -1;
1795 CSToUse.addVariableRowFill(R.Coefficients);
1796
1797 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
1799 }
1800}
1801
1804 bool Changed = false;
1805 IRBuilder<> Builder(II->getParent(), II->getIterator());
1806 Value *Sub = nullptr;
1807 for (User *U : make_early_inc_range(II->users())) {
1808 if (match(U, m_ExtractValue<0>(m_Value()))) {
1809 if (!Sub)
1810 Sub = Builder.CreateSub(A, B);
1811 U->replaceAllUsesWith(Sub);
1812 Changed = true;
1813 } else if (match(U, m_ExtractValue<1>(m_Value()))) {
1814 U->replaceAllUsesWith(Builder.getFalse());
1815 Changed = true;
1816 } else
1817 continue;
1818
1819 if (U->use_empty()) {
1820 auto *I = cast<Instruction>(U);
1821 ToRemove.push_back(I);
1822 I->setOperand(0, PoisonValue::get(II->getType()));
1823 Changed = true;
1824 }
1825 }
1826
1827 if (II->use_empty()) {
1828 II->eraseFromParent();
1829 Changed = true;
1830 }
1831 return Changed;
1832}
1833
1834static bool
1837 auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B,
1838 ConstraintInfo &Info) {
1839 auto R = Info.getConstraintForSolving(Pred, A, B);
1840 if (R.size() < 2 || !R.isValid(Info))
1841 return false;
1842
1843 auto &CSToUse = Info.getCS(R.IsSigned);
1844 return CSToUse.isConditionImplied(R.Coefficients);
1845 };
1846
1847 bool Changed = false;
1848 if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow) {
1849 // If A s>= B && B s>= 0, ssub.with.overflow(a, b) should not overflow and
1850 // can be simplified to a regular sub.
1851 Value *A = II->getArgOperand(0);
1852 Value *B = II->getArgOperand(1);
1853 if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) ||
1854 !DoesConditionHold(CmpInst::ICMP_SGE, B,
1855 ConstantInt::get(A->getType(), 0), Info))
1856 return false;
1857 Changed = replaceSubOverflowUses(II, A, B, ToRemove);
1858 }
1859 return Changed;
1860}
1861
1863 ScalarEvolution &SE,
1865 TargetLibraryInfo &TLI) {
1866 bool Changed = false;
1867 DT.updateDFSNumbers();
1868 SmallVector<Value *> FunctionArgs(llvm::make_pointer_range(F.args()));
1869 ConstraintInfo Info(F.getDataLayout(), FunctionArgs);
1870 State S(DT, LI, SE, TLI);
1871 std::unique_ptr<Module> ReproducerModule(
1872 DumpReproducers ? new Module(F.getName(), F.getContext()) : nullptr);
1873
1874 // First, collect conditions implied by branches and blocks with their
1875 // Dominator DFS in and out numbers.
1876 for (BasicBlock &BB : F) {
1877 if (!DT.getNode(&BB))
1878 continue;
1879 S.addInfoFor(BB);
1880 }
1881
1882 // Next, sort worklist by dominance, so that dominating conditions to check
1883 // and facts come before conditions and facts dominated by them. If a
1884 // condition to check and a fact have the same numbers, conditional facts come
1885 // first. Assume facts and checks are ordered according to their relative
1886 // order in the containing basic block. Also make sure conditions with
1887 // constant operands come before conditions without constant operands. This
1888 // increases the effectiveness of the current signed <-> unsigned fact
1889 // transfer logic.
1890 stable_sort(S.WorkList, [](const FactOrCheck &A, const FactOrCheck &B) {
1891 auto HasNoConstOp = [](const FactOrCheck &B) {
1892 Value *V0 = B.isConditionFact() ? B.Cond.Op0 : B.Inst->getOperand(0);
1893 Value *V1 = B.isConditionFact() ? B.Cond.Op1 : B.Inst->getOperand(1);
1894 return !isa<ConstantInt>(V0) && !isa<ConstantInt>(V1);
1895 };
1896 // If both entries have the same In numbers, conditional facts come first.
1897 // Otherwise use the relative order in the basic block.
1898 if (A.NumIn == B.NumIn) {
1899 if (A.isConditionFact() && B.isConditionFact()) {
1900 bool NoConstOpA = HasNoConstOp(A);
1901 bool NoConstOpB = HasNoConstOp(B);
1902 return NoConstOpA < NoConstOpB;
1903 }
1904 if (A.isConditionFact())
1905 return true;
1906 if (B.isConditionFact())
1907 return false;
1908 auto *InstA = A.getContextInst();
1909 auto *InstB = B.getContextInst();
1910 return InstA->comesBefore(InstB);
1911 }
1912 return A.NumIn < B.NumIn;
1913 });
1914
1916
1917 // Finally, process ordered worklist and eliminate implied conditions.
1918 SmallVector<StackEntry, 16> DFSInStack;
1919 SmallVector<ReproducerEntry> ReproducerCondStack;
1920 for (FactOrCheck &CB : S.WorkList) {
1921 // First, pop entries from the stack that are out-of-scope for CB. Remove
1922 // the corresponding entry from the constraint system.
1923 while (!DFSInStack.empty()) {
1924 auto &E = DFSInStack.back();
1925 LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
1926 << "\n");
1927 LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
1928 assert(E.NumIn <= CB.NumIn);
1929 if (CB.NumOut <= E.NumOut)
1930 break;
1931 LLVM_DEBUG({
1932 dbgs() << "Removing ";
1933 dumpConstraint(Info.getCS(E.IsSigned).getLastConstraint(),
1934 Info.getValue2Index(E.IsSigned));
1935 dbgs() << "\n";
1936 });
1937 removeEntryFromStack(E, Info, ReproducerModule.get(), ReproducerCondStack,
1938 DFSInStack);
1939 }
1940
1941 // For a block, check if any CmpInsts become known based on the current set
1942 // of constraints.
1943 if (CB.isCheck()) {
1944 Instruction *Inst = CB.getInstructionToSimplify();
1945 if (!Inst)
1946 continue;
1947 LLVM_DEBUG(dbgs() << "Processing condition to simplify: " << *Inst
1948 << "\n");
1949 if (auto *II = dyn_cast<WithOverflowInst>(Inst)) {
1950 Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove);
1951 } else if (auto *Cmp = dyn_cast<ICmpInst>(Inst)) {
1953 Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),
1954 ReproducerModule.get(), ReproducerCondStack, S.DT, ToRemove);
1955 if (!Simplified &&
1956 match(CB.getContextInst(), m_LogicalOp(m_Value(), m_Value()))) {
1958 CB, Info, ReproducerModule.get(), ReproducerCondStack, DFSInStack,
1959 ToRemove);
1960 }
1961 Changed |= Simplified;
1962 } else if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(Inst)) {
1963 Changed |= checkAndReplaceMinMax(MinMax, Info, ToRemove);
1964 } else if (auto *CmpIntr = dyn_cast<CmpIntrinsic>(Inst)) {
1965 Changed |= checkAndReplaceCmp(CmpIntr, Info, ToRemove);
1966 }
1967 continue;
1968 }
1969
1970 auto AddFact = [&](CmpPredicate Pred, Value *A, Value *B) {
1971 LLVM_DEBUG(dbgs() << "Processing fact to add to the system: ";
1972 dumpUnpackedICmp(dbgs(), Pred, A, B); dbgs() << "\n");
1973 if (Info.getCS(CmpInst::isSigned(Pred)).size() > MaxRows) {
1974 LLVM_DEBUG(
1975 dbgs()
1976 << "Skip adding constraint because system has too many rows.\n");
1977 return;
1978 }
1979
1980 Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
1981 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size())
1982 ReproducerCondStack.emplace_back(Pred, A, B);
1983
1984 if (ICmpInst::isRelational(Pred)) {
1985 // If samesign is present on the ICmp, simply flip the sign of the
1986 // predicate, transferring the information from the signed system to the
1987 // unsigned system, and viceversa.
1988 if (Pred.hasSameSign())
1990 CB.NumIn, CB.NumOut, DFSInStack);
1991 else
1992 Info.transferToOtherSystem(Pred, A, B, CB.NumIn, CB.NumOut,
1993 DFSInStack);
1994 }
1995
1996 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size()) {
1997 // Add dummy entries to ReproducerCondStack to keep it in sync with
1998 // DFSInStack.
1999 for (unsigned I = 0,
2000 E = (DFSInStack.size() - ReproducerCondStack.size());
2001 I < E; ++I) {
2002 ReproducerCondStack.emplace_back(ICmpInst::BAD_ICMP_PREDICATE,
2003 nullptr, nullptr);
2004 }
2005 }
2006 };
2007
2008 CmpPredicate Pred;
2009 if (!CB.isConditionFact()) {
2010 Value *X;
2011 if (match(CB.Inst, m_Intrinsic<Intrinsic::abs>(m_Value(X)))) {
2012 // If is_int_min_poison is true then we may assume llvm.abs >= 0.
2013 if (cast<ConstantInt>(CB.Inst->getOperand(1))->isOne())
2014 AddFact(CmpInst::ICMP_SGE, CB.Inst,
2015 ConstantInt::get(CB.Inst->getType(), 0));
2016 AddFact(CmpInst::ICMP_SGE, CB.Inst, X);
2017 continue;
2018 }
2019
2020 if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(CB.Inst)) {
2021 Pred = ICmpInst::getNonStrictPredicate(MinMax->getPredicate());
2022 AddFact(Pred, MinMax, MinMax->getLHS());
2023 AddFact(Pred, MinMax, MinMax->getRHS());
2024 continue;
2025 }
2026 if (auto *USatI = dyn_cast<SaturatingInst>(CB.Inst)) {
2027 switch (USatI->getIntrinsicID()) {
2028 default:
2029 llvm_unreachable("Unexpected intrinsic.");
2030 case Intrinsic::uadd_sat:
2031 AddFact(ICmpInst::ICMP_UGE, USatI, USatI->getLHS());
2032 AddFact(ICmpInst::ICMP_UGE, USatI, USatI->getRHS());
2033 break;
2034 case Intrinsic::usub_sat:
2035 AddFact(ICmpInst::ICMP_ULE, USatI, USatI->getLHS());
2036 break;
2037 }
2038 continue;
2039 }
2040
2041 auto &DL = F.getDataLayout();
2042 auto AddFactsAboutIndices = [&](Value *Ptr, Type *AccessType) {
2043 CmpPredicate Pred;
2044 Value *A, *B;
2046 *cast<GetElementPtrInst>(Ptr),
2047 DL.getTypeStoreSize(AccessType).getFixedValue(), Pred, A, B, DL,
2048 TLI))
2049 AddFact(Pred, A, B);
2050 };
2051
2052 if (auto *LI = dyn_cast<LoadInst>(CB.Inst)) {
2053 AddFactsAboutIndices(LI->getPointerOperand(), LI->getAccessType());
2054 continue;
2055 }
2056 if (auto *SI = dyn_cast<StoreInst>(CB.Inst)) {
2057 AddFactsAboutIndices(SI->getPointerOperand(), SI->getAccessType());
2058 continue;
2059 }
2060 }
2061
2062 Value *A = nullptr, *B = nullptr;
2063 if (CB.isConditionFact()) {
2064 Pred = CB.Cond.Pred;
2065 A = CB.Cond.Op0;
2066 B = CB.Cond.Op1;
2067 if (CB.DoesHold.Pred != CmpInst::BAD_ICMP_PREDICATE &&
2068 !Info.doesHold(CB.DoesHold.Pred, CB.DoesHold.Op0, CB.DoesHold.Op1)) {
2069 LLVM_DEBUG({
2070 dbgs() << "Not adding fact ";
2071 dumpUnpackedICmp(dbgs(), Pred, A, B);
2072 dbgs() << " because precondition ";
2073 dumpUnpackedICmp(dbgs(), CB.DoesHold.Pred, CB.DoesHold.Op0,
2074 CB.DoesHold.Op1);
2075 dbgs() << " does not hold.\n";
2076 });
2077 continue;
2078 }
2079 } else {
2080 bool Matched = match(CB.Inst, m_Intrinsic<Intrinsic::assume>(
2081 m_ICmp(Pred, m_Value(A), m_Value(B))));
2082 (void)Matched;
2083 assert(Matched && "Must have an assume intrinsic with a icmp operand");
2084 }
2085 AddFact(Pred, A, B);
2086 }
2087
2088 if (ReproducerModule && !ReproducerModule->functions().empty()) {
2089 std::string S;
2090 raw_string_ostream StringS(S);
2091 ReproducerModule->print(StringS, nullptr);
2092 OptimizationRemark Rem(DEBUG_TYPE, "Reproducer", &F);
2093 Rem << ore::NV("module") << S;
2094 ORE.emit(Rem);
2095 }
2096
2097#ifndef NDEBUG
2098 unsigned SignedEntries =
2099 count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; });
2100 assert(Info.getCS(false).size() - FunctionArgs.size() ==
2101 DFSInStack.size() - SignedEntries &&
2102 "updates to CS and DFSInStack are out of sync");
2103 assert(Info.getCS(true).size() == SignedEntries &&
2104 "updates to CS and DFSInStack are out of sync");
2105#endif
2106
2107 for (Instruction *I : ToRemove)
2108 I->eraseFromParent();
2109 return Changed;
2110}
2111
2114 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
2115 auto &LI = AM.getResult<LoopAnalysis>(F);
2116 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
2118 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
2119 if (!eliminateConstraints(F, DT, LI, SE, ORE, TLI))
2120 return PreservedAnalyses::all();
2121
2124 PA.preserve<LoopAnalysis>();
2127 return PA;
2128}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
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 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 cl::opt< bool > DumpReproducers("constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden, cl::desc("Dump IR to reproduce successful transformations."))
static bool checkOrAndOpImpliedByOther(FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule, SmallVectorImpl< ReproducerEntry > &ReproducerCondStack, SmallVectorImpl< StackEntry > &DFSInStack, SmallVectorImpl< Instruction * > &ToRemove)
Check if either the first condition of an AND or OR is implied by the (negated in case of OR) second ...
static bool eliminateConstraints(Function &F, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, OptimizationRemarkEmitter &ORE, TargetLibraryInfo &TLI)
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 bool checkAndReplaceCondition(ICmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut, Instruction *ContextInst, Module *ReproducerModule, ArrayRef< ReproducerEntry > ReproducerCondStack, DominatorTree &DT, SmallVectorImpl< Instruction * > &ToRemove)
static bool getConstraintFromMemoryAccess(GetElementPtrInst &GEP, uint64_t AccessSize, CmpPredicate &Pred, Value *&A, Value *&B, const DataLayout &DL, const TargetLibraryInfo &TLI)
static void dumpUnpackedICmp(raw_ostream &OS, ICmpInst::Predicate Pred, Value *LHS, Value *RHS)
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 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:194
uint64_t Size
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1328
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
Module.h This file contains the declarations for the Module class.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
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_>.
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
#define LLVM_DEBUG(...)
Definition: Debug.h:119
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:1201
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:380
LLVM_ABI APInt urem(const APInt &RHS) const
Unsigned remainder operation.
Definition: APInt.cpp:1666
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:329
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:475
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1130
bool isOne() const
Determine if this is a value of 1.
Definition: APInt.h:389
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:255
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:412
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:62
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:206
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
Definition: BasicBlock.cpp:252
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:233
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:73
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:666
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:984
bool isEquality() const
Determine if this is an equals/not equals predicate.
Definition: InstrTypes.h:917
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:678
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:707
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:708
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:702
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:701
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:705
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:703
@ ICMP_EQ
equal
Definition: InstrTypes.h:699
@ ICMP_NE
not equal
Definition: InstrTypes.h:700
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:706
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:704
bool isSigned() const
Definition: InstrTypes.h:932
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:829
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:791
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:767
This class represents a ucmp/scmp intrinsic.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
Definition: CmpPredicate.h:23
bool hasSameSign() const
Query samesign information, for optimizations.
Definition: CmpPredicate.h:43
This is the shared class of boolean and integer constants.
Definition: Constants.h:87
bool isNegative() const
Definition: Constants.h:209
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
Definition: Constants.h:131
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:169
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:154
static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
Definition: Constants.cpp:882
This is an important base class in LLVM.
Definition: Constant.h:43
static LLVM_ABI Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:420
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:373
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
DenseMap< Value *, unsigned > & getValue2Index()
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
LLVM_ABI 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)
LLVM_ABI 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:88
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:165
bool erase(const KeyT &Val)
Definition: DenseMap.h:303
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition: DenseMap.h:156
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:214
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:284
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:165
LLVM_ABI 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:135
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:166
Represents flags for the getelementptr instruction/expression.
static GEPNoWrapFlags none()
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:949
This instruction compares its operands according to the predicate given to the constructor.
Predicate getFlippedSignednessPredicate() const
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
Predicate getUnsignedPredicate() const
For example, EQ->EQ, SLE->ULE, UGT->UGT, etc.
LLVM_ABI CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles={})
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
Definition: IRBuilder.cpp:463
ConstantInt * getTrue()
Get the constant value for i1 true.
Definition: IRBuilder.h:502
BasicBlock::iterator GetInsertPoint() const
Definition: IRBuilder.h:202
ReturnInst * CreateRet(Value *V)
Create a 'ret <val>' instruction.
Definition: IRBuilder.h:1172
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1420
ConstantInt * getFalse()
Get the constant value for i1 false.
Definition: IRBuilder.h:507
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:207
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2439
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2780
LLVM_ABI void insertBefore(InstListType::iterator InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified position.
LLVM_ABI void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs={})
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1673
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:510
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:49
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:570
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
size_type size() const
Definition: MapVector.h:56
This class represents min/max intrinsics.
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
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 LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1885
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:118
PreservedAnalyses & preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:151
PreservedAnalyses & preserve()
Mark an analysis as preserved.
Definition: Analysis.h:132
This class represents an analyzed expression in the program.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
LLVM_ABI APInt getConstantMultiple(const SCEV *S)
Returns the max constant multiple of S.
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI 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:401
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:541
bool empty() const
Definition: SmallVector.h:82
size_t size() const
Definition: SmallVector.h:79
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:574
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:938
void push_back(const T &Elt)
Definition: SmallVector.h:414
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1197
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:267
LLVM_ABI unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:240
LLVM_ABI unsigned getIntegerBitWidth() const
A Use represents the edge between a Value definition and its users.
Definition: Use.h:35
Value * getOperand(unsigned i) const
Definition: User.h:232
iterator find(const KeyT &Val)
Definition: ValueMap.h:160
iterator end()
Definition: ValueMap.h:139
LLVM Value Representation.
Definition: Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:546
LLVM_ABI 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:5305
LLVM_ABI const Value * stripPointerCastsSameRepresentation() const
Strip off pointer casts, all-zero GEPs and address space casts but ensures the representation of the ...
Definition: Value.cpp:709
bool use_empty() const
Definition: Value.h:346
constexpr ScalarTy getFixedValue() const
Definition: TypeSize.h:203
constexpr bool isFixed() const
Returns true if the quantity is not scaled by vscale.
Definition: TypeSize.h:175
const ParentTy * getParent() const
Definition: ilist_node.h:34
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:662
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ 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.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
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
NoWrapTrunc_match< OpTy, TruncInst::NoSignedWrap > m_NSWTrunc(const OpTy &Op)
Matches trunc nsw.
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)
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, 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:444
@ 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
@ Offset
Definition: DWP.cpp:477
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:758
void stable_sort(R &&Range)
Definition: STLExtras.h:2077
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:1744
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:1702
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
Definition: Verifier.cpp:7513
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2155
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:663
LLVM_ABI std::optional< TypeSize > getBaseObjectSize(const Value *Ptr, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Like getObjectSize(), but only returns the size of base objects (like allocas, global variables and a...
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
constexpr unsigned MaxAnalysisRecursionDepth
Definition: ValueTracking.h:47
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1669
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:207
@ Sub
Subtraction of integers.
LLVM_ABI void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:223
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:1886
LLVM_ABI 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:1980
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
Definition: iterator.h:363
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:706
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:732
LLVM_ABI 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.
LLVM_ABI bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the give value is known to be non-negative.
LLVM_ABI void findDbgUsers(Value *V, SmallVectorImpl< DbgVariableRecord * > &DbgVariableRecords)
Finds the debug info records describing a value.
Definition: DebugInfo.cpp:129
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:851
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
#define N
Various options to control the behavior of getObjectSize.
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can't be evaluated.
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables.
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:249