1 | //===- llvm/Analysis/ValueTracking.h - Walk computations --------*- C++ -*-===// |
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 | // This file contains routines that help analyze properties that chains of |
10 | // computations have. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_ANALYSIS_VALUETRACKING_H |
15 | #define LLVM_ANALYSIS_VALUETRACKING_H |
16 | |
17 | #include "llvm/ADT/ArrayRef.h" |
18 | #include "llvm/Analysis/SimplifyQuery.h" |
19 | #include "llvm/Analysis/WithCache.h" |
20 | #include "llvm/IR/Constants.h" |
21 | #include "llvm/IR/DataLayout.h" |
22 | #include "llvm/IR/FMF.h" |
23 | #include "llvm/IR/InstrTypes.h" |
24 | #include "llvm/IR/Intrinsics.h" |
25 | #include <cassert> |
26 | #include <cstdint> |
27 | |
28 | namespace llvm { |
29 | |
30 | class Operator; |
31 | class AddOperator; |
32 | class AllocaInst; |
33 | class APInt; |
34 | class AssumptionCache; |
35 | class DominatorTree; |
36 | class GEPOperator; |
37 | class LoadInst; |
38 | class WithOverflowInst; |
39 | struct KnownBits; |
40 | class Loop; |
41 | class LoopInfo; |
42 | class MDNode; |
43 | class StringRef; |
44 | class TargetLibraryInfo; |
45 | class Value; |
46 | |
47 | constexpr unsigned MaxAnalysisRecursionDepth = 6; |
48 | |
49 | /// Determine which bits of V are known to be either zero or one and return |
50 | /// them in the KnownZero/KnownOne bit sets. |
51 | /// |
52 | /// This function is defined on values with integer type, values with pointer |
53 | /// type, and vectors of integers. In the case |
54 | /// where V is a vector, the known zero and known one values are the |
55 | /// same width as the vector element, and the bit is set only if it is true |
56 | /// for all of the elements in the vector. |
57 | void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, |
58 | unsigned Depth = 0, AssumptionCache *AC = nullptr, |
59 | const Instruction *CxtI = nullptr, |
60 | const DominatorTree *DT = nullptr, |
61 | bool UseInstrInfo = true); |
62 | |
63 | /// Returns the known bits rather than passing by reference. |
64 | KnownBits computeKnownBits(const Value *V, const DataLayout &DL, |
65 | unsigned Depth = 0, AssumptionCache *AC = nullptr, |
66 | const Instruction *CxtI = nullptr, |
67 | const DominatorTree *DT = nullptr, |
68 | bool UseInstrInfo = true); |
69 | |
70 | /// Returns the known bits rather than passing by reference. |
71 | KnownBits computeKnownBits(const Value *V, const APInt &DemandedElts, |
72 | const DataLayout &DL, unsigned Depth = 0, |
73 | AssumptionCache *AC = nullptr, |
74 | const Instruction *CxtI = nullptr, |
75 | const DominatorTree *DT = nullptr, |
76 | bool UseInstrInfo = true); |
77 | |
78 | KnownBits computeKnownBits(const Value *V, const APInt &DemandedElts, |
79 | unsigned Depth, const SimplifyQuery &Q); |
80 | |
81 | KnownBits computeKnownBits(const Value *V, unsigned Depth, |
82 | const SimplifyQuery &Q); |
83 | |
84 | void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, |
85 | const SimplifyQuery &Q); |
86 | |
87 | /// Compute known bits from the range metadata. |
88 | /// \p KnownZero the set of bits that are known to be zero |
89 | /// \p KnownOne the set of bits that are known to be one |
90 | void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, KnownBits &Known); |
91 | |
92 | /// Merge bits known from context-dependent facts into Known. |
93 | void computeKnownBitsFromContext(const Value *V, KnownBits &Known, |
94 | unsigned Depth, const SimplifyQuery &Q); |
95 | |
96 | /// Using KnownBits LHS/RHS produce the known bits for logic op (and/xor/or). |
97 | KnownBits analyzeKnownBitsFromAndXorOr(const Operator *I, |
98 | const KnownBits &KnownLHS, |
99 | const KnownBits &KnownRHS, |
100 | unsigned Depth, const SimplifyQuery &SQ); |
101 | |
102 | /// Return true if LHS and RHS have no common bits set. |
103 | bool haveNoCommonBitsSet(const WithCache<const Value *> &LHSCache, |
104 | const WithCache<const Value *> &RHSCache, |
105 | const SimplifyQuery &SQ); |
106 | |
107 | /// Return true if the given value is known to have exactly one bit set when |
108 | /// defined. For vectors return true if every element is known to be a power |
109 | /// of two when defined. Supports values with integer or pointer type and |
110 | /// vectors of integers. If 'OrZero' is set, then return true if the given |
111 | /// value is either a power of two or zero. |
112 | bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, |
113 | bool OrZero = false, unsigned Depth = 0, |
114 | AssumptionCache *AC = nullptr, |
115 | const Instruction *CxtI = nullptr, |
116 | const DominatorTree *DT = nullptr, |
117 | bool UseInstrInfo = true); |
118 | |
119 | bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI); |
120 | |
121 | /// Return true if the given value is known to be non-zero when defined. For |
122 | /// vectors, return true if every element is known to be non-zero when |
123 | /// defined. For pointers, if the context instruction and dominator tree are |
124 | /// specified, perform context-sensitive analysis and return true if the |
125 | /// pointer couldn't possibly be null at the specified instruction. |
126 | /// Supports values with integer or pointer type and vectors of integers. |
127 | bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth = 0, |
128 | AssumptionCache *AC = nullptr, |
129 | const Instruction *CxtI = nullptr, |
130 | const DominatorTree *DT = nullptr, |
131 | bool UseInstrInfo = true); |
132 | |
133 | /// Return true if the two given values are negation. |
134 | /// Currently can recoginze Value pair: |
135 | /// 1: <X, Y> if X = sub (0, Y) or Y = sub (0, X) |
136 | /// 2: <X, Y> if X = sub (A, B) and Y = sub (B, A) |
137 | bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW = false); |
138 | |
139 | /// Returns true if the give value is known to be non-negative. |
140 | bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, |
141 | unsigned Depth = 0); |
142 | |
143 | /// Returns true if the given value is known be positive (i.e. non-negative |
144 | /// and non-zero). |
145 | bool isKnownPositive(const Value *V, const SimplifyQuery &SQ, |
146 | unsigned Depth = 0); |
147 | |
148 | /// Returns true if the given value is known be negative (i.e. non-positive |
149 | /// and non-zero). |
150 | bool isKnownNegative(const Value *V, const SimplifyQuery &DL, |
151 | unsigned Depth = 0); |
152 | |
153 | /// Return true if the given values are known to be non-equal when defined. |
154 | /// Supports scalar integer types only. |
155 | bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL, |
156 | AssumptionCache *AC = nullptr, |
157 | const Instruction *CxtI = nullptr, |
158 | const DominatorTree *DT = nullptr, |
159 | bool UseInstrInfo = true); |
160 | |
161 | /// Return true if 'V & Mask' is known to be zero. We use this predicate to |
162 | /// simplify operations downstream. Mask is known to be zero for bits that V |
163 | /// cannot have. |
164 | /// |
165 | /// This function is defined on values with integer type, values with pointer |
166 | /// type, and vectors of integers. In the case |
167 | /// where V is a vector, the mask, known zero, and known one values are the |
168 | /// same width as the vector element, and the bit is set only if it is true |
169 | /// for all of the elements in the vector. |
170 | bool MaskedValueIsZero(const Value *V, const APInt &Mask, |
171 | const SimplifyQuery &DL, unsigned Depth = 0); |
172 | |
173 | /// Return the number of times the sign bit of the register is replicated into |
174 | /// the other bits. We know that at least 1 bit is always equal to the sign |
175 | /// bit (itself), but other cases can give us information. For example, |
176 | /// immediately after an "ashr X, 2", we know that the top 3 bits are all |
177 | /// equal to each other, so we return 3. For vectors, return the number of |
178 | /// sign bits for the vector element with the mininum number of known sign |
179 | /// bits. |
180 | unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, |
181 | unsigned Depth = 0, AssumptionCache *AC = nullptr, |
182 | const Instruction *CxtI = nullptr, |
183 | const DominatorTree *DT = nullptr, |
184 | bool UseInstrInfo = true); |
185 | |
186 | /// Get the upper bound on bit size for this Value \p Op as a signed integer. |
187 | /// i.e. x == sext(trunc(x to MaxSignificantBits) to bitwidth(x)). |
188 | /// Similar to the APInt::getSignificantBits function. |
189 | unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, |
190 | unsigned Depth = 0, |
191 | AssumptionCache *AC = nullptr, |
192 | const Instruction *CxtI = nullptr, |
193 | const DominatorTree *DT = nullptr); |
194 | |
195 | /// Map a call instruction to an intrinsic ID. Libcalls which have equivalent |
196 | /// intrinsics are treated as-if they were intrinsics. |
197 | Intrinsic::ID getIntrinsicForCallSite(const CallBase &CB, |
198 | const TargetLibraryInfo *TLI); |
199 | |
200 | /// Given an exploded icmp instruction, return true if the comparison only |
201 | /// checks the sign bit. If it only checks the sign bit, set TrueIfSigned if |
202 | /// the result of the comparison is true when the input value is signed. |
203 | bool isSignBitCheck(ICmpInst::Predicate Pred, const APInt &RHS, |
204 | bool &TrueIfSigned); |
205 | |
206 | /// Returns a pair of values, which if passed to llvm.is.fpclass, returns the |
207 | /// same result as an fcmp with the given operands. |
208 | /// |
209 | /// If \p LookThroughSrc is true, consider the input value when computing the |
210 | /// mask. |
211 | /// |
212 | /// If \p LookThroughSrc is false, ignore the source value (i.e. the first pair |
213 | /// element will always be LHS. |
214 | std::pair<Value *, FPClassTest> fcmpToClassTest(CmpInst::Predicate Pred, |
215 | const Function &F, Value *LHS, |
216 | Value *RHS, |
217 | bool LookThroughSrc = true); |
218 | std::pair<Value *, FPClassTest> fcmpToClassTest(CmpInst::Predicate Pred, |
219 | const Function &F, Value *LHS, |
220 | const APFloat *ConstRHS, |
221 | bool LookThroughSrc = true); |
222 | |
223 | /// Compute the possible floating-point classes that \p LHS could be based on |
224 | /// fcmp \Pred \p LHS, \p RHS. |
225 | /// |
226 | /// \returns { TestedValue, ClassesIfTrue, ClassesIfFalse } |
227 | /// |
228 | /// If the compare returns an exact class test, ClassesIfTrue == ~ClassesIfFalse |
229 | /// |
230 | /// This is a less exact version of fcmpToClassTest (e.g. fcmpToClassTest will |
231 | /// only succeed for a test of x > 0 implies positive, but not x > 1). |
232 | /// |
233 | /// If \p LookThroughSrc is true, consider the input value when computing the |
234 | /// mask. This may look through sign bit operations. |
235 | /// |
236 | /// If \p LookThroughSrc is false, ignore the source value (i.e. the first pair |
237 | /// element will always be LHS. |
238 | /// |
239 | std::tuple<Value *, FPClassTest, FPClassTest> |
240 | fcmpImpliesClass(CmpInst::Predicate Pred, const Function &F, Value *LHS, |
241 | Value *RHS, bool LookThroughSrc = true); |
242 | std::tuple<Value *, FPClassTest, FPClassTest> |
243 | fcmpImpliesClass(CmpInst::Predicate Pred, const Function &F, Value *LHS, |
244 | FPClassTest RHS, bool LookThroughSrc = true); |
245 | std::tuple<Value *, FPClassTest, FPClassTest> |
246 | fcmpImpliesClass(CmpInst::Predicate Pred, const Function &F, Value *LHS, |
247 | const APFloat &RHS, bool LookThroughSrc = true); |
248 | |
249 | struct KnownFPClass { |
250 | /// Floating-point classes the value could be one of. |
251 | FPClassTest KnownFPClasses = fcAllFlags; |
252 | |
253 | /// std::nullopt if the sign bit is unknown, true if the sign bit is |
254 | /// definitely set or false if the sign bit is definitely unset. |
255 | std::optional<bool> SignBit; |
256 | |
257 | bool operator==(KnownFPClass Other) const { |
258 | return KnownFPClasses == Other.KnownFPClasses && SignBit == Other.SignBit; |
259 | } |
260 | |
261 | /// Return true if it's known this can never be one of the mask entries. |
262 | bool isKnownNever(FPClassTest Mask) const { |
263 | return (KnownFPClasses & Mask) == fcNone; |
264 | } |
265 | |
266 | bool isUnknown() const { |
267 | return KnownFPClasses == fcAllFlags && !SignBit; |
268 | } |
269 | |
270 | /// Return true if it's known this can never be a nan. |
271 | bool isKnownNeverNaN() const { |
272 | return isKnownNever(Mask: fcNan); |
273 | } |
274 | |
275 | /// Return true if it's known this can never be an infinity. |
276 | bool isKnownNeverInfinity() const { |
277 | return isKnownNever(Mask: fcInf); |
278 | } |
279 | |
280 | /// Return true if it's known this can never be +infinity. |
281 | bool isKnownNeverPosInfinity() const { |
282 | return isKnownNever(Mask: fcPosInf); |
283 | } |
284 | |
285 | /// Return true if it's known this can never be -infinity. |
286 | bool isKnownNeverNegInfinity() const { |
287 | return isKnownNever(Mask: fcNegInf); |
288 | } |
289 | |
290 | /// Return true if it's known this can never be a subnormal |
291 | bool isKnownNeverSubnormal() const { |
292 | return isKnownNever(Mask: fcSubnormal); |
293 | } |
294 | |
295 | /// Return true if it's known this can never be a positive subnormal |
296 | bool isKnownNeverPosSubnormal() const { |
297 | return isKnownNever(Mask: fcPosSubnormal); |
298 | } |
299 | |
300 | /// Return true if it's known this can never be a negative subnormal |
301 | bool isKnownNeverNegSubnormal() const { |
302 | return isKnownNever(Mask: fcNegSubnormal); |
303 | } |
304 | |
305 | /// Return true if it's known this can never be a zero. This means a literal |
306 | /// [+-]0, and does not include denormal inputs implicitly treated as [+-]0. |
307 | bool isKnownNeverZero() const { |
308 | return isKnownNever(Mask: fcZero); |
309 | } |
310 | |
311 | /// Return true if it's known this can never be a literal positive zero. |
312 | bool isKnownNeverPosZero() const { |
313 | return isKnownNever(Mask: fcPosZero); |
314 | } |
315 | |
316 | /// Return true if it's known this can never be a negative zero. This means a |
317 | /// literal -0 and does not include denormal inputs implicitly treated as -0. |
318 | bool isKnownNeverNegZero() const { |
319 | return isKnownNever(Mask: fcNegZero); |
320 | } |
321 | |
322 | /// Return true if it's know this can never be interpreted as a zero. This |
323 | /// extends isKnownNeverZero to cover the case where the assumed |
324 | /// floating-point mode for the function interprets denormals as zero. |
325 | bool isKnownNeverLogicalZero(const Function &F, Type *Ty) const; |
326 | |
327 | /// Return true if it's know this can never be interpreted as a negative zero. |
328 | bool isKnownNeverLogicalNegZero(const Function &F, Type *Ty) const; |
329 | |
330 | /// Return true if it's know this can never be interpreted as a positive zero. |
331 | bool isKnownNeverLogicalPosZero(const Function &F, Type *Ty) const; |
332 | |
333 | static constexpr FPClassTest OrderedLessThanZeroMask = |
334 | fcNegSubnormal | fcNegNormal | fcNegInf; |
335 | static constexpr FPClassTest OrderedGreaterThanZeroMask = |
336 | fcPosSubnormal | fcPosNormal | fcPosInf; |
337 | |
338 | /// Return true if we can prove that the analyzed floating-point value is |
339 | /// either NaN or never less than -0.0. |
340 | /// |
341 | /// NaN --> true |
342 | /// +0 --> true |
343 | /// -0 --> true |
344 | /// x > +0 --> true |
345 | /// x < -0 --> false |
346 | bool cannotBeOrderedLessThanZero() const { |
347 | return isKnownNever(Mask: OrderedLessThanZeroMask); |
348 | } |
349 | |
350 | /// Return true if we can prove that the analyzed floating-point value is |
351 | /// either NaN or never greater than -0.0. |
352 | /// NaN --> true |
353 | /// +0 --> true |
354 | /// -0 --> true |
355 | /// x > +0 --> false |
356 | /// x < -0 --> true |
357 | bool cannotBeOrderedGreaterThanZero() const { |
358 | return isKnownNever(Mask: OrderedGreaterThanZeroMask); |
359 | } |
360 | |
361 | KnownFPClass &operator|=(const KnownFPClass &RHS) { |
362 | KnownFPClasses = KnownFPClasses | RHS.KnownFPClasses; |
363 | |
364 | if (SignBit != RHS.SignBit) |
365 | SignBit = std::nullopt; |
366 | return *this; |
367 | } |
368 | |
369 | void knownNot(FPClassTest RuleOut) { |
370 | KnownFPClasses = KnownFPClasses & ~RuleOut; |
371 | if (isKnownNever(Mask: fcNan) && !SignBit) { |
372 | if (isKnownNever(Mask: fcNegative)) |
373 | SignBit = false; |
374 | else if (isKnownNever(Mask: fcPositive)) |
375 | SignBit = true; |
376 | } |
377 | } |
378 | |
379 | void fneg() { |
380 | KnownFPClasses = llvm::fneg(Mask: KnownFPClasses); |
381 | if (SignBit) |
382 | SignBit = !*SignBit; |
383 | } |
384 | |
385 | void fabs() { |
386 | if (KnownFPClasses & fcNegZero) |
387 | KnownFPClasses |= fcPosZero; |
388 | |
389 | if (KnownFPClasses & fcNegInf) |
390 | KnownFPClasses |= fcPosInf; |
391 | |
392 | if (KnownFPClasses & fcNegSubnormal) |
393 | KnownFPClasses |= fcPosSubnormal; |
394 | |
395 | if (KnownFPClasses & fcNegNormal) |
396 | KnownFPClasses |= fcPosNormal; |
397 | |
398 | signBitMustBeZero(); |
399 | } |
400 | |
401 | /// Return true if the sign bit must be 0, ignoring the sign of nans. |
402 | bool signBitIsZeroOrNaN() const { |
403 | return isKnownNever(Mask: fcNegative); |
404 | } |
405 | |
406 | /// Assume the sign bit is zero. |
407 | void signBitMustBeZero() { |
408 | KnownFPClasses &= (fcPositive | fcNan); |
409 | SignBit = false; |
410 | } |
411 | |
412 | /// Assume the sign bit is one. |
413 | void signBitMustBeOne() { |
414 | KnownFPClasses &= (fcNegative | fcNan); |
415 | SignBit = true; |
416 | } |
417 | |
418 | void copysign(const KnownFPClass &Sign) { |
419 | // Don't know anything about the sign of the source. Expand the possible set |
420 | // to its opposite sign pair. |
421 | if (KnownFPClasses & fcZero) |
422 | KnownFPClasses |= fcZero; |
423 | if (KnownFPClasses & fcSubnormal) |
424 | KnownFPClasses |= fcSubnormal; |
425 | if (KnownFPClasses & fcNormal) |
426 | KnownFPClasses |= fcNormal; |
427 | if (KnownFPClasses & fcInf) |
428 | KnownFPClasses |= fcInf; |
429 | |
430 | // Sign bit is exactly preserved even for nans. |
431 | SignBit = Sign.SignBit; |
432 | |
433 | // Clear sign bits based on the input sign mask. |
434 | if (Sign.isKnownNever(Mask: fcPositive | fcNan) || (SignBit && *SignBit)) |
435 | KnownFPClasses &= (fcNegative | fcNan); |
436 | if (Sign.isKnownNever(Mask: fcNegative | fcNan) || (SignBit && !*SignBit)) |
437 | KnownFPClasses &= (fcPositive | fcNan); |
438 | } |
439 | |
440 | // Propagate knowledge that a non-NaN source implies the result can also not |
441 | // be a NaN. For unconstrained operations, signaling nans are not guaranteed |
442 | // to be quieted but cannot be introduced. |
443 | void propagateNaN(const KnownFPClass &Src, bool PreserveSign = false) { |
444 | if (Src.isKnownNever(Mask: fcNan)) { |
445 | knownNot(RuleOut: fcNan); |
446 | if (PreserveSign) |
447 | SignBit = Src.SignBit; |
448 | } else if (Src.isKnownNever(Mask: fcSNan)) |
449 | knownNot(RuleOut: fcSNan); |
450 | } |
451 | |
452 | /// Propagate knowledge from a source value that could be a denormal or |
453 | /// zero. We have to be conservative since output flushing is not guaranteed, |
454 | /// so known-never-zero may not hold. |
455 | /// |
456 | /// This assumes a copy-like operation and will replace any currently known |
457 | /// information. |
458 | void propagateDenormal(const KnownFPClass &Src, const Function &F, Type *Ty); |
459 | |
460 | /// Report known classes if \p Src is evaluated through a potentially |
461 | /// canonicalizing operation. We can assume signaling nans will not be |
462 | /// introduced, but cannot assume a denormal will be flushed under FTZ/DAZ. |
463 | /// |
464 | /// This assumes a copy-like operation and will replace any currently known |
465 | /// information. |
466 | void propagateCanonicalizingSrc(const KnownFPClass &Src, const Function &F, |
467 | Type *Ty); |
468 | |
469 | void resetAll() { *this = KnownFPClass(); } |
470 | }; |
471 | |
472 | inline KnownFPClass operator|(KnownFPClass LHS, const KnownFPClass &RHS) { |
473 | LHS |= RHS; |
474 | return LHS; |
475 | } |
476 | |
477 | inline KnownFPClass operator|(const KnownFPClass &LHS, KnownFPClass &&RHS) { |
478 | RHS |= LHS; |
479 | return std::move(RHS); |
480 | } |
481 | |
482 | /// Determine which floating-point classes are valid for \p V, and return them |
483 | /// in KnownFPClass bit sets. |
484 | /// |
485 | /// This function is defined on values with floating-point type, values vectors |
486 | /// of floating-point type, and arrays of floating-point type. |
487 | |
488 | /// \p InterestedClasses is a compile time optimization hint for which floating |
489 | /// point classes should be queried. Queries not specified in \p |
490 | /// InterestedClasses should be reliable if they are determined during the |
491 | /// query. |
492 | KnownFPClass computeKnownFPClass(const Value *V, const APInt &DemandedElts, |
493 | FPClassTest InterestedClasses, unsigned Depth, |
494 | const SimplifyQuery &SQ); |
495 | |
496 | KnownFPClass computeKnownFPClass(const Value *V, FPClassTest InterestedClasses, |
497 | unsigned Depth, const SimplifyQuery &SQ); |
498 | |
499 | inline KnownFPClass computeKnownFPClass( |
500 | const Value *V, const DataLayout &DL, |
501 | FPClassTest InterestedClasses = fcAllFlags, unsigned Depth = 0, |
502 | const TargetLibraryInfo *TLI = nullptr, AssumptionCache *AC = nullptr, |
503 | const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr, |
504 | bool UseInstrInfo = true) { |
505 | return computeKnownFPClass( |
506 | V, InterestedClasses, Depth, |
507 | SQ: SimplifyQuery(DL, TLI, DT, AC, CxtI, UseInstrInfo)); |
508 | } |
509 | |
510 | /// Wrapper to account for known fast math flags at the use instruction. |
511 | inline KnownFPClass computeKnownFPClass(const Value *V, FastMathFlags FMF, |
512 | FPClassTest InterestedClasses, |
513 | unsigned Depth, |
514 | const SimplifyQuery &SQ) { |
515 | if (FMF.noNaNs()) |
516 | InterestedClasses &= ~fcNan; |
517 | if (FMF.noInfs()) |
518 | InterestedClasses &= ~fcInf; |
519 | |
520 | KnownFPClass Result = computeKnownFPClass(V, InterestedClasses, Depth, SQ); |
521 | |
522 | if (FMF.noNaNs()) |
523 | Result.KnownFPClasses &= ~fcNan; |
524 | if (FMF.noInfs()) |
525 | Result.KnownFPClasses &= ~fcInf; |
526 | return Result; |
527 | } |
528 | |
529 | /// Return true if we can prove that the specified FP value is never equal to |
530 | /// -0.0. Users should use caution when considering PreserveSign |
531 | /// denormal-fp-math. |
532 | inline bool cannotBeNegativeZero(const Value *V, unsigned Depth, |
533 | const SimplifyQuery &SQ) { |
534 | KnownFPClass Known = computeKnownFPClass(V, InterestedClasses: fcNegZero, Depth, SQ); |
535 | return Known.isKnownNeverNegZero(); |
536 | } |
537 | |
538 | /// Return true if we can prove that the specified FP value is either NaN or |
539 | /// never less than -0.0. |
540 | /// |
541 | /// NaN --> true |
542 | /// +0 --> true |
543 | /// -0 --> true |
544 | /// x > +0 --> true |
545 | /// x < -0 --> false |
546 | inline bool cannotBeOrderedLessThanZero(const Value *V, unsigned Depth, |
547 | const SimplifyQuery &SQ) { |
548 | KnownFPClass Known = |
549 | computeKnownFPClass(V, InterestedClasses: KnownFPClass::OrderedLessThanZeroMask, Depth, SQ); |
550 | return Known.cannotBeOrderedLessThanZero(); |
551 | } |
552 | |
553 | /// Return true if the floating-point scalar value is not an infinity or if |
554 | /// the floating-point vector value has no infinities. Return false if a value |
555 | /// could ever be infinity. |
556 | inline bool isKnownNeverInfinity(const Value *V, unsigned Depth, |
557 | const SimplifyQuery &SQ) { |
558 | KnownFPClass Known = computeKnownFPClass(V, InterestedClasses: fcInf, Depth, SQ); |
559 | return Known.isKnownNeverInfinity(); |
560 | } |
561 | |
562 | /// Return true if the floating-point value can never contain a NaN or infinity. |
563 | inline bool isKnownNeverInfOrNaN(const Value *V, unsigned Depth, |
564 | const SimplifyQuery &SQ) { |
565 | KnownFPClass Known = computeKnownFPClass(V, InterestedClasses: fcInf | fcNan, Depth, SQ); |
566 | return Known.isKnownNeverNaN() && Known.isKnownNeverInfinity(); |
567 | } |
568 | |
569 | /// Return true if the floating-point scalar value is not a NaN or if the |
570 | /// floating-point vector value has no NaN elements. Return false if a value |
571 | /// could ever be NaN. |
572 | inline bool isKnownNeverNaN(const Value *V, unsigned Depth, |
573 | const SimplifyQuery &SQ) { |
574 | KnownFPClass Known = computeKnownFPClass(V, InterestedClasses: fcNan, Depth, SQ); |
575 | return Known.isKnownNeverNaN(); |
576 | } |
577 | |
578 | /// Return false if we can prove that the specified FP value's sign bit is 0. |
579 | /// Return true if we can prove that the specified FP value's sign bit is 1. |
580 | /// Otherwise return std::nullopt. |
581 | inline std::optional<bool> computeKnownFPSignBit(const Value *V, unsigned Depth, |
582 | const SimplifyQuery &SQ) { |
583 | KnownFPClass Known = computeKnownFPClass(V, InterestedClasses: fcAllFlags, Depth, SQ); |
584 | return Known.SignBit; |
585 | } |
586 | |
587 | /// If the specified value can be set by repeating the same byte in memory, |
588 | /// return the i8 value that it is represented with. This is true for all i8 |
589 | /// values obviously, but is also true for i32 0, i32 -1, i16 0xF0F0, double |
590 | /// 0.0 etc. If the value can't be handled with a repeated byte store (e.g. |
591 | /// i16 0x1234), return null. If the value is entirely undef and padding, |
592 | /// return undef. |
593 | Value *isBytewiseValue(Value *V, const DataLayout &DL); |
594 | |
595 | /// Given an aggregate and an sequence of indices, see if the scalar value |
596 | /// indexed is already around as a register, for example if it were inserted |
597 | /// directly into the aggregate. |
598 | /// |
599 | /// If InsertBefore is not null, this function will duplicate (modified) |
600 | /// insertvalues when a part of a nested struct is extracted. |
601 | Value *FindInsertedValue(Value *V, ArrayRef<unsigned> idx_range, |
602 | Instruction *InsertBefore = nullptr); |
603 | |
604 | /// Analyze the specified pointer to see if it can be expressed as a base |
605 | /// pointer plus a constant offset. Return the base and offset to the caller. |
606 | /// |
607 | /// This is a wrapper around Value::stripAndAccumulateConstantOffsets that |
608 | /// creates and later unpacks the required APInt. |
609 | inline Value *GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, |
610 | const DataLayout &DL, |
611 | bool AllowNonInbounds = true) { |
612 | APInt OffsetAPInt(DL.getIndexTypeSizeInBits(Ty: Ptr->getType()), 0); |
613 | Value *Base = |
614 | Ptr->stripAndAccumulateConstantOffsets(DL, Offset&: OffsetAPInt, AllowNonInbounds); |
615 | |
616 | Offset = OffsetAPInt.getSExtValue(); |
617 | return Base; |
618 | } |
619 | inline const Value * |
620 | GetPointerBaseWithConstantOffset(const Value *Ptr, int64_t &Offset, |
621 | const DataLayout &DL, |
622 | bool AllowNonInbounds = true) { |
623 | return GetPointerBaseWithConstantOffset(Ptr: const_cast<Value *>(Ptr), Offset, DL, |
624 | AllowNonInbounds); |
625 | } |
626 | |
627 | /// Returns true if the GEP is based on a pointer to a string (array of |
628 | // \p CharSize integers) and is indexing into this string. |
629 | bool isGEPBasedOnPointerToString(const GEPOperator *GEP, unsigned CharSize = 8); |
630 | |
631 | /// Represents offset+length into a ConstantDataArray. |
632 | struct ConstantDataArraySlice { |
633 | /// ConstantDataArray pointer. nullptr indicates a zeroinitializer (a valid |
634 | /// initializer, it just doesn't fit the ConstantDataArray interface). |
635 | const ConstantDataArray *Array; |
636 | |
637 | /// Slice starts at this Offset. |
638 | uint64_t Offset; |
639 | |
640 | /// Length of the slice. |
641 | uint64_t Length; |
642 | |
643 | /// Moves the Offset and adjusts Length accordingly. |
644 | void move(uint64_t Delta) { |
645 | assert(Delta < Length); |
646 | Offset += Delta; |
647 | Length -= Delta; |
648 | } |
649 | |
650 | /// Convenience accessor for elements in the slice. |
651 | uint64_t operator[](unsigned I) const { |
652 | return Array == nullptr ? 0 : Array->getElementAsInteger(i: I + Offset); |
653 | } |
654 | }; |
655 | |
656 | /// Returns true if the value \p V is a pointer into a ConstantDataArray. |
657 | /// If successful \p Slice will point to a ConstantDataArray info object |
658 | /// with an appropriate offset. |
659 | bool getConstantDataArrayInfo(const Value *V, ConstantDataArraySlice &Slice, |
660 | unsigned ElementSize, uint64_t Offset = 0); |
661 | |
662 | /// This function computes the length of a null-terminated C string pointed to |
663 | /// by V. If successful, it returns true and returns the string in Str. If |
664 | /// unsuccessful, it returns false. This does not include the trailing null |
665 | /// character by default. If TrimAtNul is set to false, then this returns any |
666 | /// trailing null characters as well as any other characters that come after |
667 | /// it. |
668 | bool getConstantStringInfo(const Value *V, StringRef &Str, |
669 | bool TrimAtNul = true); |
670 | |
671 | /// If we can compute the length of the string pointed to by the specified |
672 | /// pointer, return 'len+1'. If we can't, return 0. |
673 | uint64_t GetStringLength(const Value *V, unsigned CharSize = 8); |
674 | |
675 | /// This function returns call pointer argument that is considered the same by |
676 | /// aliasing rules. You CAN'T use it to replace one value with another. If |
677 | /// \p MustPreserveNullness is true, the call must preserve the nullness of |
678 | /// the pointer. |
679 | const Value *getArgumentAliasingToReturnedPointer(const CallBase *Call, |
680 | bool MustPreserveNullness); |
681 | inline Value *getArgumentAliasingToReturnedPointer(CallBase *Call, |
682 | bool MustPreserveNullness) { |
683 | return const_cast<Value *>(getArgumentAliasingToReturnedPointer( |
684 | Call: const_cast<const CallBase *>(Call), MustPreserveNullness)); |
685 | } |
686 | |
687 | /// {launder,strip}.invariant.group returns pointer that aliases its argument, |
688 | /// and it only captures pointer by returning it. |
689 | /// These intrinsics are not marked as nocapture, because returning is |
690 | /// considered as capture. The arguments are not marked as returned neither, |
691 | /// because it would make it useless. If \p MustPreserveNullness is true, |
692 | /// the intrinsic must preserve the nullness of the pointer. |
693 | bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing( |
694 | const CallBase *Call, bool MustPreserveNullness); |
695 | |
696 | /// This method strips off any GEP address adjustments and pointer casts from |
697 | /// the specified value, returning the original object being addressed. Note |
698 | /// that the returned value has pointer type if the specified value does. If |
699 | /// the MaxLookup value is non-zero, it limits the number of instructions to |
700 | /// be stripped off. |
701 | const Value *getUnderlyingObject(const Value *V, unsigned MaxLookup = 6); |
702 | inline Value *getUnderlyingObject(Value *V, unsigned MaxLookup = 6) { |
703 | // Force const to avoid infinite recursion. |
704 | const Value *VConst = V; |
705 | return const_cast<Value *>(getUnderlyingObject(V: VConst, MaxLookup)); |
706 | } |
707 | |
708 | /// This method is similar to getUnderlyingObject except that it can |
709 | /// look through phi and select instructions and return multiple objects. |
710 | /// |
711 | /// If LoopInfo is passed, loop phis are further analyzed. If a pointer |
712 | /// accesses different objects in each iteration, we don't look through the |
713 | /// phi node. E.g. consider this loop nest: |
714 | /// |
715 | /// int **A; |
716 | /// for (i) |
717 | /// for (j) { |
718 | /// A[i][j] = A[i-1][j] * B[j] |
719 | /// } |
720 | /// |
721 | /// This is transformed by Load-PRE to stash away A[i] for the next iteration |
722 | /// of the outer loop: |
723 | /// |
724 | /// Curr = A[0]; // Prev_0 |
725 | /// for (i: 1..N) { |
726 | /// Prev = Curr; // Prev = PHI (Prev_0, Curr) |
727 | /// Curr = A[i]; |
728 | /// for (j: 0..N) { |
729 | /// Curr[j] = Prev[j] * B[j] |
730 | /// } |
731 | /// } |
732 | /// |
733 | /// Since A[i] and A[i-1] are independent pointers, getUnderlyingObjects |
734 | /// should not assume that Curr and Prev share the same underlying object thus |
735 | /// it shouldn't look through the phi above. |
736 | void getUnderlyingObjects(const Value *V, |
737 | SmallVectorImpl<const Value *> &Objects, |
738 | LoopInfo *LI = nullptr, unsigned MaxLookup = 6); |
739 | |
740 | /// This is a wrapper around getUnderlyingObjects and adds support for basic |
741 | /// ptrtoint+arithmetic+inttoptr sequences. |
742 | bool getUnderlyingObjectsForCodeGen(const Value *V, |
743 | SmallVectorImpl<Value *> &Objects); |
744 | |
745 | /// Returns unique alloca where the value comes from, or nullptr. |
746 | /// If OffsetZero is true check that V points to the begining of the alloca. |
747 | AllocaInst *findAllocaForValue(Value *V, bool OffsetZero = false); |
748 | inline const AllocaInst *findAllocaForValue(const Value *V, |
749 | bool OffsetZero = false) { |
750 | return findAllocaForValue(V: const_cast<Value *>(V), OffsetZero); |
751 | } |
752 | |
753 | /// Return true if the only users of this pointer are lifetime markers. |
754 | bool onlyUsedByLifetimeMarkers(const Value *V); |
755 | |
756 | /// Return true if the only users of this pointer are lifetime markers or |
757 | /// droppable instructions. |
758 | bool onlyUsedByLifetimeMarkersOrDroppableInsts(const Value *V); |
759 | |
760 | /// Return true if speculation of the given load must be suppressed to avoid |
761 | /// ordering or interfering with an active sanitizer. If not suppressed, |
762 | /// dereferenceability and alignment must be proven separately. Note: This |
763 | /// is only needed for raw reasoning; if you use the interface below |
764 | /// (isSafeToSpeculativelyExecute), this is handled internally. |
765 | bool mustSuppressSpeculation(const LoadInst &LI); |
766 | |
767 | /// Return true if the instruction does not have any effects besides |
768 | /// calculating the result and does not have undefined behavior. |
769 | /// |
770 | /// This method never returns true for an instruction that returns true for |
771 | /// mayHaveSideEffects; however, this method also does some other checks in |
772 | /// addition. It checks for undefined behavior, like dividing by zero or |
773 | /// loading from an invalid pointer (but not for undefined results, like a |
774 | /// shift with a shift amount larger than the width of the result). It checks |
775 | /// for malloc and alloca because speculatively executing them might cause a |
776 | /// memory leak. It also returns false for instructions related to control |
777 | /// flow, specifically terminators and PHI nodes. |
778 | /// |
779 | /// If the CtxI is specified this method performs context-sensitive analysis |
780 | /// and returns true if it is safe to execute the instruction immediately |
781 | /// before the CtxI. |
782 | /// |
783 | /// If the CtxI is NOT specified this method only looks at the instruction |
784 | /// itself and its operands, so if this method returns true, it is safe to |
785 | /// move the instruction as long as the correct dominance relationships for |
786 | /// the operands and users hold. |
787 | /// |
788 | /// This method can return true for instructions that read memory; |
789 | /// for such instructions, moving them may change the resulting value. |
790 | bool isSafeToSpeculativelyExecute(const Instruction *I, |
791 | const Instruction *CtxI = nullptr, |
792 | AssumptionCache *AC = nullptr, |
793 | const DominatorTree *DT = nullptr, |
794 | const TargetLibraryInfo *TLI = nullptr); |
795 | |
796 | /// This returns the same result as isSafeToSpeculativelyExecute if Opcode is |
797 | /// the actual opcode of Inst. If the provided and actual opcode differ, the |
798 | /// function (virtually) overrides the opcode of Inst with the provided |
799 | /// Opcode. There are come constraints in this case: |
800 | /// * If Opcode has a fixed number of operands (eg, as binary operators do), |
801 | /// then Inst has to have at least as many leading operands. The function |
802 | /// will ignore all trailing operands beyond that number. |
803 | /// * If Opcode allows for an arbitrary number of operands (eg, as CallInsts |
804 | /// do), then all operands are considered. |
805 | /// * The virtual instruction has to satisfy all typing rules of the provided |
806 | /// Opcode. |
807 | /// * This function is pessimistic in the following sense: If one actually |
808 | /// materialized the virtual instruction, then isSafeToSpeculativelyExecute |
809 | /// may say that the materialized instruction is speculatable whereas this |
810 | /// function may have said that the instruction wouldn't be speculatable. |
811 | /// This behavior is a shortcoming in the current implementation and not |
812 | /// intentional. |
813 | bool isSafeToSpeculativelyExecuteWithOpcode( |
814 | unsigned Opcode, const Instruction *Inst, const Instruction *CtxI = nullptr, |
815 | AssumptionCache *AC = nullptr, const DominatorTree *DT = nullptr, |
816 | const TargetLibraryInfo *TLI = nullptr); |
817 | |
818 | /// Returns true if the result or effects of the given instructions \p I |
819 | /// depend values not reachable through the def use graph. |
820 | /// * Memory dependence arises for example if the instruction reads from |
821 | /// memory or may produce effects or undefined behaviour. Memory dependent |
822 | /// instructions generally cannot be reorderd with respect to other memory |
823 | /// dependent instructions. |
824 | /// * Control dependence arises for example if the instruction may fault |
825 | /// if lifted above a throwing call or infinite loop. |
826 | bool mayHaveNonDefUseDependency(const Instruction &I); |
827 | |
828 | /// Return true if it is an intrinsic that cannot be speculated but also |
829 | /// cannot trap. |
830 | bool isAssumeLikeIntrinsic(const Instruction *I); |
831 | |
832 | /// Return true if it is valid to use the assumptions provided by an |
833 | /// assume intrinsic, I, at the point in the control-flow identified by the |
834 | /// context instruction, CxtI. By default, ephemeral values of the assumption |
835 | /// are treated as an invalid context, to prevent the assumption from being used |
836 | /// to optimize away its argument. If the caller can ensure that this won't |
837 | /// happen, it can call with AllowEphemerals set to true to get more valid |
838 | /// assumptions. |
839 | bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, |
840 | const DominatorTree *DT = nullptr, |
841 | bool AllowEphemerals = false); |
842 | |
843 | enum class OverflowResult { |
844 | /// Always overflows in the direction of signed/unsigned min value. |
845 | AlwaysOverflowsLow, |
846 | /// Always overflows in the direction of signed/unsigned max value. |
847 | AlwaysOverflowsHigh, |
848 | /// May or may not overflow. |
849 | MayOverflow, |
850 | /// Never overflows. |
851 | NeverOverflows, |
852 | }; |
853 | |
854 | OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, |
855 | const SimplifyQuery &SQ); |
856 | OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, |
857 | const SimplifyQuery &SQ); |
858 | OverflowResult |
859 | computeOverflowForUnsignedAdd(const WithCache<const Value *> &LHS, |
860 | const WithCache<const Value *> &RHS, |
861 | const SimplifyQuery &SQ); |
862 | OverflowResult computeOverflowForSignedAdd(const WithCache<const Value *> &LHS, |
863 | const WithCache<const Value *> &RHS, |
864 | const SimplifyQuery &SQ); |
865 | /// This version also leverages the sign bit of Add if known. |
866 | OverflowResult computeOverflowForSignedAdd(const AddOperator *Add, |
867 | const SimplifyQuery &SQ); |
868 | OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, |
869 | const SimplifyQuery &SQ); |
870 | OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, |
871 | const SimplifyQuery &SQ); |
872 | |
873 | /// Returns true if the arithmetic part of the \p WO 's result is |
874 | /// used only along the paths control dependent on the computation |
875 | /// not overflowing, \p WO being an <op>.with.overflow intrinsic. |
876 | bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO, |
877 | const DominatorTree &DT); |
878 | |
879 | /// Determine the possible constant range of vscale with the given bit width, |
880 | /// based on the vscale_range function attribute. |
881 | ConstantRange getVScaleRange(const Function *F, unsigned BitWidth); |
882 | |
883 | /// Determine the possible constant range of an integer or vector of integer |
884 | /// value. This is intended as a cheap, non-recursive check. |
885 | ConstantRange computeConstantRange(const Value *V, bool ForSigned, |
886 | bool UseInstrInfo = true, |
887 | AssumptionCache *AC = nullptr, |
888 | const Instruction *CtxI = nullptr, |
889 | const DominatorTree *DT = nullptr, |
890 | unsigned Depth = 0); |
891 | |
892 | /// Combine constant ranges from computeConstantRange() and computeKnownBits(). |
893 | ConstantRange |
894 | computeConstantRangeIncludingKnownBits(const WithCache<const Value *> &V, |
895 | bool ForSigned, const SimplifyQuery &SQ); |
896 | |
897 | /// Return true if this function can prove that the instruction I will |
898 | /// always transfer execution to one of its successors (including the next |
899 | /// instruction that follows within a basic block). E.g. this is not |
900 | /// guaranteed for function calls that could loop infinitely. |
901 | /// |
902 | /// In other words, this function returns false for instructions that may |
903 | /// transfer execution or fail to transfer execution in a way that is not |
904 | /// captured in the CFG nor in the sequence of instructions within a basic |
905 | /// block. |
906 | /// |
907 | /// Undefined behavior is assumed not to happen, so e.g. division is |
908 | /// guaranteed to transfer execution to the following instruction even |
909 | /// though division by zero might cause undefined behavior. |
910 | bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I); |
911 | |
912 | /// Returns true if this block does not contain a potential implicit exit. |
913 | /// This is equivelent to saying that all instructions within the basic block |
914 | /// are guaranteed to transfer execution to their successor within the basic |
915 | /// block. This has the same assumptions w.r.t. undefined behavior as the |
916 | /// instruction variant of this function. |
917 | bool isGuaranteedToTransferExecutionToSuccessor(const BasicBlock *BB); |
918 | |
919 | /// Return true if every instruction in the range (Begin, End) is |
920 | /// guaranteed to transfer execution to its static successor. \p ScanLimit |
921 | /// bounds the search to avoid scanning huge blocks. |
922 | bool isGuaranteedToTransferExecutionToSuccessor( |
923 | BasicBlock::const_iterator Begin, BasicBlock::const_iterator End, |
924 | unsigned ScanLimit = 32); |
925 | |
926 | /// Same as previous, but with range expressed via iterator_range. |
927 | bool isGuaranteedToTransferExecutionToSuccessor( |
928 | iterator_range<BasicBlock::const_iterator> Range, unsigned ScanLimit = 32); |
929 | |
930 | /// Return true if this function can prove that the instruction I |
931 | /// is executed for every iteration of the loop L. |
932 | /// |
933 | /// Note that this currently only considers the loop header. |
934 | bool isGuaranteedToExecuteForEveryIteration(const Instruction *I, |
935 | const Loop *L); |
936 | |
937 | /// Return true if \p PoisonOp's user yields poison or raises UB if its |
938 | /// operand \p PoisonOp is poison. |
939 | /// |
940 | /// If \p PoisonOp is a vector or an aggregate and the operation's result is a |
941 | /// single value, any poison element in /p PoisonOp should make the result |
942 | /// poison or raise UB. |
943 | /// |
944 | /// To filter out operands that raise UB on poison, you can use |
945 | /// getGuaranteedNonPoisonOp. |
946 | bool propagatesPoison(const Use &PoisonOp); |
947 | |
948 | /// Insert operands of I into Ops such that I will trigger undefined behavior |
949 | /// if I is executed and that operand has a poison value. |
950 | void getGuaranteedNonPoisonOps(const Instruction *I, |
951 | SmallVectorImpl<const Value *> &Ops); |
952 | |
953 | /// Insert operands of I into Ops such that I will trigger undefined behavior |
954 | /// if I is executed and that operand is not a well-defined value |
955 | /// (i.e. has undef bits or poison). |
956 | void getGuaranteedWellDefinedOps(const Instruction *I, |
957 | SmallVectorImpl<const Value *> &Ops); |
958 | |
959 | /// Return true if the given instruction must trigger undefined behavior |
960 | /// when I is executed with any operands which appear in KnownPoison holding |
961 | /// a poison value at the point of execution. |
962 | bool mustTriggerUB(const Instruction *I, |
963 | const SmallPtrSetImpl<const Value *> &KnownPoison); |
964 | |
965 | /// Return true if this function can prove that if Inst is executed |
966 | /// and yields a poison value or undef bits, then that will trigger |
967 | /// undefined behavior. |
968 | /// |
969 | /// Note that this currently only considers the basic block that is |
970 | /// the parent of Inst. |
971 | bool programUndefinedIfUndefOrPoison(const Instruction *Inst); |
972 | bool programUndefinedIfPoison(const Instruction *Inst); |
973 | |
974 | /// canCreateUndefOrPoison returns true if Op can create undef or poison from |
975 | /// non-undef & non-poison operands. |
976 | /// For vectors, canCreateUndefOrPoison returns true if there is potential |
977 | /// poison or undef in any element of the result when vectors without |
978 | /// undef/poison poison are given as operands. |
979 | /// For example, given `Op = shl <2 x i32> %x, <0, 32>`, this function returns |
980 | /// true. If Op raises immediate UB but never creates poison or undef |
981 | /// (e.g. sdiv I, 0), canCreatePoison returns false. |
982 | /// |
983 | /// \p ConsiderFlagsAndMetadata controls whether poison producing flags and |
984 | /// metadata on the instruction are considered. This can be used to see if the |
985 | /// instruction could still introduce undef or poison even without poison |
986 | /// generating flags and metadata which might be on the instruction. |
987 | /// (i.e. could the result of Op->dropPoisonGeneratingFlags() still create |
988 | /// poison or undef) |
989 | /// |
990 | /// canCreatePoison returns true if Op can create poison from non-poison |
991 | /// operands. |
992 | bool canCreateUndefOrPoison(const Operator *Op, |
993 | bool ConsiderFlagsAndMetadata = true); |
994 | bool canCreatePoison(const Operator *Op, bool ConsiderFlagsAndMetadata = true); |
995 | |
996 | /// Return true if V is poison given that ValAssumedPoison is already poison. |
997 | /// For example, if ValAssumedPoison is `icmp X, 10` and V is `icmp X, 5`, |
998 | /// impliesPoison returns true. |
999 | bool impliesPoison(const Value *ValAssumedPoison, const Value *V); |
1000 | |
1001 | /// Return true if this function can prove that V does not have undef bits |
1002 | /// and is never poison. If V is an aggregate value or vector, check whether |
1003 | /// all elements (except padding) are not undef or poison. |
1004 | /// Note that this is different from canCreateUndefOrPoison because the |
1005 | /// function assumes Op's operands are not poison/undef. |
1006 | /// |
1007 | /// If CtxI and DT are specified this method performs flow-sensitive analysis |
1008 | /// and returns true if it is guaranteed to be never undef or poison |
1009 | /// immediately before the CtxI. |
1010 | bool isGuaranteedNotToBeUndefOrPoison(const Value *V, |
1011 | AssumptionCache *AC = nullptr, |
1012 | const Instruction *CtxI = nullptr, |
1013 | const DominatorTree *DT = nullptr, |
1014 | unsigned Depth = 0); |
1015 | |
1016 | /// Returns true if V cannot be poison, but may be undef. |
1017 | bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC = nullptr, |
1018 | const Instruction *CtxI = nullptr, |
1019 | const DominatorTree *DT = nullptr, |
1020 | unsigned Depth = 0); |
1021 | |
1022 | /// Returns true if V cannot be undef, but may be poison. |
1023 | bool isGuaranteedNotToBeUndef(const Value *V, AssumptionCache *AC = nullptr, |
1024 | const Instruction *CtxI = nullptr, |
1025 | const DominatorTree *DT = nullptr, |
1026 | unsigned Depth = 0); |
1027 | |
1028 | /// Return true if undefined behavior would provable be executed on the path to |
1029 | /// OnPathTo if Root produced a posion result. Note that this doesn't say |
1030 | /// anything about whether OnPathTo is actually executed or whether Root is |
1031 | /// actually poison. This can be used to assess whether a new use of Root can |
1032 | /// be added at a location which is control equivalent with OnPathTo (such as |
1033 | /// immediately before it) without introducing UB which didn't previously |
1034 | /// exist. Note that a false result conveys no information. |
1035 | bool mustExecuteUBIfPoisonOnPathTo(Instruction *Root, |
1036 | Instruction *OnPathTo, |
1037 | DominatorTree *DT); |
1038 | |
1039 | /// Specific patterns of select instructions we can match. |
1040 | enum SelectPatternFlavor { |
1041 | SPF_UNKNOWN = 0, |
1042 | SPF_SMIN, /// Signed minimum |
1043 | SPF_UMIN, /// Unsigned minimum |
1044 | SPF_SMAX, /// Signed maximum |
1045 | SPF_UMAX, /// Unsigned maximum |
1046 | SPF_FMINNUM, /// Floating point minnum |
1047 | SPF_FMAXNUM, /// Floating point maxnum |
1048 | SPF_ABS, /// Absolute value |
1049 | SPF_NABS /// Negated absolute value |
1050 | }; |
1051 | |
1052 | /// Behavior when a floating point min/max is given one NaN and one |
1053 | /// non-NaN as input. |
1054 | enum SelectPatternNaNBehavior { |
1055 | SPNB_NA = 0, /// NaN behavior not applicable. |
1056 | SPNB_RETURNS_NAN, /// Given one NaN input, returns the NaN. |
1057 | SPNB_RETURNS_OTHER, /// Given one NaN input, returns the non-NaN. |
1058 | SPNB_RETURNS_ANY /// Given one NaN input, can return either (or |
1059 | /// it has been determined that no operands can |
1060 | /// be NaN). |
1061 | }; |
1062 | |
1063 | struct SelectPatternResult { |
1064 | SelectPatternFlavor Flavor; |
1065 | SelectPatternNaNBehavior NaNBehavior; /// Only applicable if Flavor is |
1066 | /// SPF_FMINNUM or SPF_FMAXNUM. |
1067 | bool Ordered; /// When implementing this min/max pattern as |
1068 | /// fcmp; select, does the fcmp have to be |
1069 | /// ordered? |
1070 | |
1071 | /// Return true if \p SPF is a min or a max pattern. |
1072 | static bool isMinOrMax(SelectPatternFlavor SPF) { |
1073 | return SPF != SPF_UNKNOWN && SPF != SPF_ABS && SPF != SPF_NABS; |
1074 | } |
1075 | }; |
1076 | |
1077 | /// Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind |
1078 | /// and providing the out parameter results if we successfully match. |
1079 | /// |
1080 | /// For ABS/NABS, LHS will be set to the input to the abs idiom. RHS will be |
1081 | /// the negation instruction from the idiom. |
1082 | /// |
1083 | /// If CastOp is not nullptr, also match MIN/MAX idioms where the type does |
1084 | /// not match that of the original select. If this is the case, the cast |
1085 | /// operation (one of Trunc,SExt,Zext) that must be done to transform the |
1086 | /// type of LHS and RHS into the type of V is returned in CastOp. |
1087 | /// |
1088 | /// For example: |
1089 | /// %1 = icmp slt i32 %a, i32 4 |
1090 | /// %2 = sext i32 %a to i64 |
1091 | /// %3 = select i1 %1, i64 %2, i64 4 |
1092 | /// |
1093 | /// -> LHS = %a, RHS = i32 4, *CastOp = Instruction::SExt |
1094 | /// |
1095 | SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, |
1096 | Instruction::CastOps *CastOp = nullptr, |
1097 | unsigned Depth = 0); |
1098 | |
1099 | inline SelectPatternResult matchSelectPattern(const Value *V, const Value *&LHS, |
1100 | const Value *&RHS) { |
1101 | Value *L = const_cast<Value *>(LHS); |
1102 | Value *R = const_cast<Value *>(RHS); |
1103 | auto Result = matchSelectPattern(V: const_cast<Value *>(V), LHS&: L, RHS&: R); |
1104 | LHS = L; |
1105 | RHS = R; |
1106 | return Result; |
1107 | } |
1108 | |
1109 | /// Determine the pattern that a select with the given compare as its |
1110 | /// predicate and given values as its true/false operands would match. |
1111 | SelectPatternResult matchDecomposedSelectPattern( |
1112 | CmpInst *CmpI, Value *TrueVal, Value *FalseVal, Value *&LHS, Value *&RHS, |
1113 | Instruction::CastOps *CastOp = nullptr, unsigned Depth = 0); |
1114 | |
1115 | /// Return the canonical comparison predicate for the specified |
1116 | /// minimum/maximum flavor. |
1117 | CmpInst::Predicate getMinMaxPred(SelectPatternFlavor SPF, bool Ordered = false); |
1118 | |
1119 | /// Return the inverse minimum/maximum flavor of the specified flavor. |
1120 | /// For example, signed minimum is the inverse of signed maximum. |
1121 | SelectPatternFlavor getInverseMinMaxFlavor(SelectPatternFlavor SPF); |
1122 | |
1123 | Intrinsic::ID getInverseMinMaxIntrinsic(Intrinsic::ID MinMaxID); |
1124 | |
1125 | /// Return the minimum or maximum constant value for the specified integer |
1126 | /// min/max flavor and type. |
1127 | APInt getMinMaxLimit(SelectPatternFlavor SPF, unsigned BitWidth); |
1128 | |
1129 | /// Check if the values in \p VL are select instructions that can be converted |
1130 | /// to a min or max (vector) intrinsic. Returns the intrinsic ID, if such a |
1131 | /// conversion is possible, together with a bool indicating whether all select |
1132 | /// conditions are only used by the selects. Otherwise return |
1133 | /// Intrinsic::not_intrinsic. |
1134 | std::pair<Intrinsic::ID, bool> |
1135 | canConvertToMinOrMaxIntrinsic(ArrayRef<Value *> VL); |
1136 | |
1137 | /// Attempt to match a simple first order recurrence cycle of the form: |
1138 | /// %iv = phi Ty [%Start, %Entry], [%Inc, %backedge] |
1139 | /// %inc = binop %iv, %step |
1140 | /// OR |
1141 | /// %iv = phi Ty [%Start, %Entry], [%Inc, %backedge] |
1142 | /// %inc = binop %step, %iv |
1143 | /// |
1144 | /// A first order recurrence is a formula with the form: X_n = f(X_(n-1)) |
1145 | /// |
1146 | /// A couple of notes on subtleties in that definition: |
1147 | /// * The Step does not have to be loop invariant. In math terms, it can |
1148 | /// be a free variable. We allow recurrences with both constant and |
1149 | /// variable coefficients. Callers may wish to filter cases where Step |
1150 | /// does not dominate P. |
1151 | /// * For non-commutative operators, we will match both forms. This |
1152 | /// results in some odd recurrence structures. Callers may wish to filter |
1153 | /// out recurrences where the phi is not the LHS of the returned operator. |
1154 | /// * Because of the structure matched, the caller can assume as a post |
1155 | /// condition of the match the presence of a Loop with P's parent as it's |
1156 | /// header *except* in unreachable code. (Dominance decays in unreachable |
1157 | /// code.) |
1158 | /// |
1159 | /// NOTE: This is intentional simple. If you want the ability to analyze |
1160 | /// non-trivial loop conditons, see ScalarEvolution instead. |
1161 | bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, |
1162 | Value *&Step); |
1163 | |
1164 | /// Analogous to the above, but starting from the binary operator |
1165 | bool matchSimpleRecurrence(const BinaryOperator *I, PHINode *&P, Value *&Start, |
1166 | Value *&Step); |
1167 | |
1168 | /// Return true if RHS is known to be implied true by LHS. Return false if |
1169 | /// RHS is known to be implied false by LHS. Otherwise, return std::nullopt if |
1170 | /// no implication can be made. A & B must be i1 (boolean) values or a vector of |
1171 | /// such values. Note that the truth table for implication is the same as <=u on |
1172 | /// i1 values (but not |
1173 | /// <=s!). The truth table for both is: |
1174 | /// | T | F (B) |
1175 | /// T | T | F |
1176 | /// F | T | T |
1177 | /// (A) |
1178 | std::optional<bool> isImpliedCondition(const Value *LHS, const Value *RHS, |
1179 | const DataLayout &DL, |
1180 | bool LHSIsTrue = true, |
1181 | unsigned Depth = 0); |
1182 | std::optional<bool> isImpliedCondition(const Value *LHS, |
1183 | CmpInst::Predicate RHSPred, |
1184 | const Value *RHSOp0, const Value *RHSOp1, |
1185 | const DataLayout &DL, |
1186 | bool LHSIsTrue = true, |
1187 | unsigned Depth = 0); |
1188 | |
1189 | /// Return the boolean condition value in the context of the given instruction |
1190 | /// if it is known based on dominating conditions. |
1191 | std::optional<bool> isImpliedByDomCondition(const Value *Cond, |
1192 | const Instruction *ContextI, |
1193 | const DataLayout &DL); |
1194 | std::optional<bool> isImpliedByDomCondition(CmpInst::Predicate Pred, |
1195 | const Value *LHS, const Value *RHS, |
1196 | const Instruction *ContextI, |
1197 | const DataLayout &DL); |
1198 | } // end namespace llvm |
1199 | |
1200 | #endif // LLVM_ANALYSIS_VALUETRACKING_H |
1201 | |