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