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