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
28namespace llvm {
29
30class Operator;
31class AddOperator;
32class AllocaInst;
33class APInt;
34class AssumptionCache;
35class DominatorTree;
36class GEPOperator;
37class LoadInst;
38class WithOverflowInst;
39struct KnownBits;
40class Loop;
41class LoopInfo;
42class MDNode;
43class StringRef;
44class TargetLibraryInfo;
45class Value;
46
47constexpr 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.
57void 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.
64KnownBits 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.
71KnownBits 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
78KnownBits computeKnownBits(const Value *V, const APInt &DemandedElts,
79 unsigned Depth, const SimplifyQuery &Q);
80
81KnownBits computeKnownBits(const Value *V, unsigned Depth,
82 const SimplifyQuery &Q);
83
84void 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
90void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, KnownBits &Known);
91
92/// Merge bits known from context-dependent facts into Known.
93void 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).
97KnownBits 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.
103bool 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.
112bool 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
119bool 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.
127bool 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)
137bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW = false);
138
139/// Returns true if the give value is known to be non-negative.
140bool 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).
145bool 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).
150bool 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.
155bool 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.
170bool 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.
180unsigned 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.
189unsigned 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.
197Intrinsic::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.
203bool 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.
214std::pair<Value *, FPClassTest> fcmpToClassTest(CmpInst::Predicate Pred,
215 const Function &F, Value *LHS,
216 Value *RHS,
217 bool LookThroughSrc = true);
218std::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///
239std::tuple<Value *, FPClassTest, FPClassTest>
240fcmpImpliesClass(CmpInst::Predicate Pred, const Function &F, Value *LHS,
241 Value *RHS, bool LookThroughSrc = true);
242std::tuple<Value *, FPClassTest, FPClassTest>
243fcmpImpliesClass(CmpInst::Predicate Pred, const Function &F, Value *LHS,
244 FPClassTest RHS, bool LookThroughSrc = true);
245std::tuple<Value *, FPClassTest, FPClassTest>
246fcmpImpliesClass(CmpInst::Predicate Pred, const Function &F, Value *LHS,
247 const APFloat &RHS, bool LookThroughSrc = true);
248
249struct 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
472inline KnownFPClass operator|(KnownFPClass LHS, const KnownFPClass &RHS) {
473 LHS |= RHS;
474 return LHS;
475}
476
477inline 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.
492KnownFPClass computeKnownFPClass(const Value *V, const APInt &DemandedElts,
493 FPClassTest InterestedClasses, unsigned Depth,
494 const SimplifyQuery &SQ);
495
496KnownFPClass computeKnownFPClass(const Value *V, FPClassTest InterestedClasses,
497 unsigned Depth, const SimplifyQuery &SQ);
498
499inline 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.
511inline 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.
532inline 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
546inline 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.
556inline 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.
563inline 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.
572inline 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.
581inline 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.
593Value *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.
601Value *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.
609inline 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}
619inline const Value *
620GetPointerBaseWithConstantOffset(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.
629bool isGEPBasedOnPointerToString(const GEPOperator *GEP, unsigned CharSize = 8);
630
631/// Represents offset+length into a ConstantDataArray.
632struct 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.
659bool 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.
668bool 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.
673uint64_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.
679const Value *getArgumentAliasingToReturnedPointer(const CallBase *Call,
680 bool MustPreserveNullness);
681inline 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.
693bool 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.
701const Value *getUnderlyingObject(const Value *V, unsigned MaxLookup = 6);
702inline 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.
736void 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.
742bool 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.
747AllocaInst *findAllocaForValue(Value *V, bool OffsetZero = false);
748inline 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.
754bool onlyUsedByLifetimeMarkers(const Value *V);
755
756/// Return true if the only users of this pointer are lifetime markers or
757/// droppable instructions.
758bool 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.
765bool 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.
790bool 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.
813bool 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.
826bool mayHaveNonDefUseDependency(const Instruction &I);
827
828/// Return true if it is an intrinsic that cannot be speculated but also
829/// cannot trap.
830bool 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.
839bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI,
840 const DominatorTree *DT = nullptr,
841 bool AllowEphemerals = false);
842
843enum 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
854OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS,
855 const SimplifyQuery &SQ);
856OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS,
857 const SimplifyQuery &SQ);
858OverflowResult
859computeOverflowForUnsignedAdd(const WithCache<const Value *> &LHS,
860 const WithCache<const Value *> &RHS,
861 const SimplifyQuery &SQ);
862OverflowResult 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.
866OverflowResult computeOverflowForSignedAdd(const AddOperator *Add,
867 const SimplifyQuery &SQ);
868OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS,
869 const SimplifyQuery &SQ);
870OverflowResult 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.
876bool 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.
881ConstantRange 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.
885ConstantRange 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().
893ConstantRange
894computeConstantRangeIncludingKnownBits(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.
910bool 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.
917bool 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.
922bool 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.
927bool 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.
934bool 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.
946bool 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.
950void 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).
956void 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.
962bool 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.
971bool programUndefinedIfUndefOrPoison(const Instruction *Inst);
972bool 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.
992bool canCreateUndefOrPoison(const Operator *Op,
993 bool ConsiderFlagsAndMetadata = true);
994bool 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.
999bool 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.
1010bool 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.
1017bool 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.
1023bool 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.
1035bool mustExecuteUBIfPoisonOnPathTo(Instruction *Root,
1036 Instruction *OnPathTo,
1037 DominatorTree *DT);
1038
1039/// Specific patterns of select instructions we can match.
1040enum 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.
1054enum 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
1063struct 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///
1095SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS,
1096 Instruction::CastOps *CastOp = nullptr,
1097 unsigned Depth = 0);
1098
1099inline 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.
1111SelectPatternResult 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.
1117CmpInst::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.
1121SelectPatternFlavor getInverseMinMaxFlavor(SelectPatternFlavor SPF);
1122
1123Intrinsic::ID getInverseMinMaxIntrinsic(Intrinsic::ID MinMaxID);
1124
1125/// Return the minimum or maximum constant value for the specified integer
1126/// min/max flavor and type.
1127APInt 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.
1134std::pair<Intrinsic::ID, bool>
1135canConvertToMinOrMaxIntrinsic(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.
1161bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start,
1162 Value *&Step);
1163
1164/// Analogous to the above, but starting from the binary operator
1165bool 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)
1178std::optional<bool> isImpliedCondition(const Value *LHS, const Value *RHS,
1179 const DataLayout &DL,
1180 bool LHSIsTrue = true,
1181 unsigned Depth = 0);
1182std::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.
1191std::optional<bool> isImpliedByDomCondition(const Value *Cond,
1192 const Instruction *ContextI,
1193 const DataLayout &DL);
1194std::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

source code of llvm/include/llvm/Analysis/ValueTracking.h