LLVM  10.0.0svn
ValueTracking.h
Go to the documentation of this file.
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/ADT/Optional.h"
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/IR/CallSite.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/DataLayout.h"
23 #include "llvm/IR/Instruction.h"
24 #include "llvm/IR/Intrinsics.h"
25 #include <cassert>
26 #include <cstdint>
27 
28 namespace llvm {
29 
30 class AddOperator;
31 class APInt;
32 class AssumptionCache;
33 class DominatorTree;
34 class GEPOperator;
35 class IntrinsicInst;
36 class WithOverflowInst;
37 struct KnownBits;
38 class Loop;
39 class LoopInfo;
40 class MDNode;
41 class OptimizationRemarkEmitter;
42 class StringRef;
43 class TargetLibraryInfo;
44 class Value;
45 
46  /// Determine which bits of V are known to be either zero or one and return
47  /// them in the KnownZero/KnownOne bit sets.
48  ///
49  /// This function is defined on values with integer type, values with pointer
50  /// type, and vectors of integers. In the case
51  /// where V is a vector, the known zero and known one values are the
52  /// same width as the vector element, and the bit is set only if it is true
53  /// for all of the elements in the vector.
54  void computeKnownBits(const Value *V, KnownBits &Known,
55  const DataLayout &DL, unsigned Depth = 0,
56  AssumptionCache *AC = nullptr,
57  const Instruction *CxtI = nullptr,
58  const DominatorTree *DT = nullptr,
59  OptimizationRemarkEmitter *ORE = nullptr,
60  bool UseInstrInfo = true);
61 
62  /// Returns the known bits rather than passing by reference.
63  KnownBits computeKnownBits(const Value *V, const DataLayout &DL,
64  unsigned Depth = 0, AssumptionCache *AC = nullptr,
65  const Instruction *CxtI = nullptr,
66  const DominatorTree *DT = nullptr,
67  OptimizationRemarkEmitter *ORE = nullptr,
68  bool UseInstrInfo = true);
69 
70  /// Compute known bits from the range metadata.
71  /// \p KnownZero the set of bits that are known to be zero
72  /// \p KnownOne the set of bits that are known to be one
73  void computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
74  KnownBits &Known);
75 
76  /// Return true if LHS and RHS have no common bits set.
77  bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS,
78  const DataLayout &DL,
79  AssumptionCache *AC = nullptr,
80  const Instruction *CxtI = nullptr,
81  const DominatorTree *DT = nullptr,
82  bool UseInstrInfo = true);
83 
84  /// Return true if the given value is known to have exactly one bit set when
85  /// defined. For vectors return true if every element is known to be a power
86  /// of two when defined. Supports values with integer or pointer type and
87  /// vectors of integers. If 'OrZero' is set, then return true if the given
88  /// value is either a power of two or zero.
89  bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL,
90  bool OrZero = false, unsigned Depth = 0,
91  AssumptionCache *AC = nullptr,
92  const Instruction *CxtI = nullptr,
93  const DominatorTree *DT = nullptr,
94  bool UseInstrInfo = true);
95 
96  bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI);
97 
98  /// Return true if the given value is known to be non-zero when defined. For
99  /// vectors, return true if every element is known to be non-zero when
100  /// defined. For pointers, if the context instruction and dominator tree are
101  /// specified, perform context-sensitive analysis and return true if the
102  /// pointer couldn't possibly be null at the specified instruction.
103  /// Supports values with integer or pointer type and vectors of integers.
104  bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth = 0,
105  AssumptionCache *AC = nullptr,
106  const Instruction *CxtI = nullptr,
107  const DominatorTree *DT = nullptr,
108  bool UseInstrInfo = true);
109 
110  /// Return true if the two given values are negation.
111  /// Currently can recoginze Value pair:
112  /// 1: <X, Y> if X = sub (0, Y) or Y = sub (0, X)
113  /// 2: <X, Y> if X = sub (A, B) and Y = sub (B, A)
114  bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW = false);
115 
116  /// Returns true if the give value is known to be non-negative.
117  bool isKnownNonNegative(const Value *V, const DataLayout &DL,
118  unsigned Depth = 0,
119  AssumptionCache *AC = nullptr,
120  const Instruction *CxtI = nullptr,
121  const DominatorTree *DT = nullptr,
122  bool UseInstrInfo = true);
123 
124  /// Returns true if the given value is known be positive (i.e. non-negative
125  /// and non-zero).
126  bool isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth = 0,
127  AssumptionCache *AC = nullptr,
128  const Instruction *CxtI = nullptr,
129  const DominatorTree *DT = nullptr,
130  bool UseInstrInfo = true);
131 
132  /// Returns true if the given value is known be negative (i.e. non-positive
133  /// and non-zero).
134  bool isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth = 0,
135  AssumptionCache *AC = nullptr,
136  const Instruction *CxtI = nullptr,
137  const DominatorTree *DT = nullptr,
138  bool UseInstrInfo = true);
139 
140  /// Return true if the given values are known to be non-equal when defined.
141  /// Supports scalar integer types only.
142  bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL,
143  AssumptionCache *AC = nullptr,
144  const Instruction *CxtI = nullptr,
145  const DominatorTree *DT = nullptr,
146  bool UseInstrInfo = true);
147 
148  /// Return true if 'V & Mask' is known to be zero. We use this predicate to
149  /// simplify operations downstream. Mask is known to be zero for bits that V
150  /// cannot have.
151  ///
152  /// This function is defined on values with integer type, values with pointer
153  /// type, and vectors of integers. In the case
154  /// where V is a vector, the mask, known zero, and known one values are the
155  /// same width as the vector element, and the bit is set only if it is true
156  /// for all of the elements in the vector.
157  bool MaskedValueIsZero(const Value *V, const APInt &Mask,
158  const DataLayout &DL,
159  unsigned Depth = 0, AssumptionCache *AC = nullptr,
160  const Instruction *CxtI = nullptr,
161  const DominatorTree *DT = nullptr,
162  bool UseInstrInfo = true);
163 
164  /// Return the number of times the sign bit of the register is replicated into
165  /// the other bits. We know that at least 1 bit is always equal to the sign
166  /// bit (itself), but other cases can give us information. For example,
167  /// immediately after an "ashr X, 2", we know that the top 3 bits are all
168  /// equal to each other, so we return 3. For vectors, return the number of
169  /// sign bits for the vector element with the mininum number of known sign
170  /// bits.
171  unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL,
172  unsigned Depth = 0, AssumptionCache *AC = nullptr,
173  const Instruction *CxtI = nullptr,
174  const DominatorTree *DT = nullptr,
175  bool UseInstrInfo = true);
176 
177  /// This function computes the integer multiple of Base that equals V. If
178  /// successful, it returns true and returns the multiple in Multiple. If
179  /// unsuccessful, it returns false. Also, if V can be simplified to an
180  /// integer, then the simplified V is returned in Val. Look through sext only
181  /// if LookThroughSExt=true.
182  bool ComputeMultiple(Value *V, unsigned Base, Value *&Multiple,
183  bool LookThroughSExt = false,
184  unsigned Depth = 0);
185 
186  /// Map a call instruction to an intrinsic ID. Libcalls which have equivalent
187  /// intrinsics are treated as-if they were intrinsics.
188  Intrinsic::ID getIntrinsicForCallSite(ImmutableCallSite ICS,
189  const TargetLibraryInfo *TLI);
190 
191  /// Return true if we can prove that the specified FP value is never equal to
192  /// -0.0.
193  bool CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI,
194  unsigned Depth = 0);
195 
196  /// Return true if we can prove that the specified FP value is either NaN or
197  /// never less than -0.0.
198  ///
199  /// NaN --> true
200  /// +0 --> true
201  /// -0 --> true
202  /// x > +0 --> true
203  /// x < -0 --> false
204  bool CannotBeOrderedLessThanZero(const Value *V, const TargetLibraryInfo *TLI);
205 
206  /// Return true if the floating-point scalar value is not a NaN or if the
207  /// floating-point vector value has no NaN elements. Return false if a value
208  /// could ever be NaN.
209  bool isKnownNeverNaN(const Value *V, const TargetLibraryInfo *TLI,
210  unsigned Depth = 0);
211 
212  /// Return true if we can prove that the specified FP value's sign bit is 0.
213  ///
214  /// NaN --> true/false (depending on the NaN's sign bit)
215  /// +0 --> true
216  /// -0 --> false
217  /// x > +0 --> true
218  /// x < -0 --> false
219  bool SignBitMustBeZero(const Value *V, const TargetLibraryInfo *TLI);
220 
221  /// If the specified value can be set by repeating the same byte in memory,
222  /// return the i8 value that it is represented with. This is true for all i8
223  /// values obviously, but is also true for i32 0, i32 -1, i16 0xF0F0, double
224  /// 0.0 etc. If the value can't be handled with a repeated byte store (e.g.
225  /// i16 0x1234), return null. If the value is entirely undef and padding,
226  /// return undef.
227  Value *isBytewiseValue(Value *V, const DataLayout &DL);
228 
229  /// Given an aggregrate and an sequence of indices, see if the scalar value
230  /// indexed is already around as a register, for example if it were inserted
231  /// directly into the aggregrate.
232  ///
233  /// If InsertBefore is not null, this function will duplicate (modified)
234  /// insertvalues when a part of a nested struct is extracted.
236  ArrayRef<unsigned> idx_range,
237  Instruction *InsertBefore = nullptr);
238 
239  /// Analyze the specified pointer to see if it can be expressed as a base
240  /// pointer plus a constant offset. Return the base and offset to the caller.
241  ///
242  /// This is a wrapper around Value::stripAndAccumulateConstantOffsets that
243  /// creates and later unpacks the required APInt.
245  const DataLayout &DL,
246  bool AllowNonInbounds = true) {
247  APInt OffsetAPInt(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
248  Value *Base =
249  Ptr->stripAndAccumulateConstantOffsets(DL, OffsetAPInt, AllowNonInbounds);
250 
251  Offset = OffsetAPInt.getSExtValue();
252  return Base;
253  }
254  inline const Value *
256  const DataLayout &DL,
257  bool AllowNonInbounds = true) {
258  return GetPointerBaseWithConstantOffset(const_cast<Value *>(Ptr), Offset, DL,
259  AllowNonInbounds);
260  }
261 
262  /// Returns true if the GEP is based on a pointer to a string (array of
263  // \p CharSize integers) and is indexing into this string.
265  unsigned CharSize = 8);
266 
267  /// Represents offset+length into a ConstantDataArray.
269  /// ConstantDataArray pointer. nullptr indicates a zeroinitializer (a valid
270  /// initializer, it just doesn't fit the ConstantDataArray interface).
272 
273  /// Slice starts at this Offset.
274  uint64_t Offset;
275 
276  /// Length of the slice.
277  uint64_t Length;
278 
279  /// Moves the Offset and adjusts Length accordingly.
280  void move(uint64_t Delta) {
281  assert(Delta < Length);
282  Offset += Delta;
283  Length -= Delta;
284  }
285 
286  /// Convenience accessor for elements in the slice.
287  uint64_t operator[](unsigned I) const {
288  return Array==nullptr ? 0 : Array->getElementAsInteger(I + Offset);
289  }
290  };
291 
292  /// Returns true if the value \p V is a pointer into a ConstantDataArray.
293  /// If successful \p Slice will point to a ConstantDataArray info object
294  /// with an appropriate offset.
296  unsigned ElementSize, uint64_t Offset = 0);
297 
298  /// This function computes the length of a null-terminated C string pointed to
299  /// by V. If successful, it returns true and returns the string in Str. If
300  /// unsuccessful, it returns false. This does not include the trailing null
301  /// character by default. If TrimAtNul is set to false, then this returns any
302  /// trailing null characters as well as any other characters that come after
303  /// it.
304  bool getConstantStringInfo(const Value *V, StringRef &Str,
305  uint64_t Offset = 0, bool TrimAtNul = true);
306 
307  /// If we can compute the length of the string pointed to by the specified
308  /// pointer, return 'len+1'. If we can't, return 0.
309  uint64_t GetStringLength(const Value *V, unsigned CharSize = 8);
310 
311  /// This function returns call pointer argument that is considered the same by
312  /// aliasing rules. You CAN'T use it to replace one value with another. If
313  /// \p MustPreserveNullness is true, the call must preserve the nullness of
314  /// the pointer.
316  bool MustPreserveNullness);
317  inline Value *
319  bool MustPreserveNullness) {
320  return const_cast<Value *>(getArgumentAliasingToReturnedPointer(
321  const_cast<const CallBase *>(Call), MustPreserveNullness));
322  }
323 
324  /// {launder,strip}.invariant.group returns pointer that aliases its argument,
325  /// and it only captures pointer by returning it.
326  /// These intrinsics are not marked as nocapture, because returning is
327  /// considered as capture. The arguments are not marked as returned neither,
328  /// because it would make it useless. If \p MustPreserveNullness is true,
329  /// the intrinsic must preserve the nullness of the pointer.
331  const CallBase *Call, bool MustPreserveNullness);
332 
333  /// This method strips off any GEP address adjustments and pointer casts from
334  /// the specified value, returning the original object being addressed. Note
335  /// that the returned value has pointer type if the specified value does. If
336  /// the MaxLookup value is non-zero, it limits the number of instructions to
337  /// be stripped off.
338  Value *GetUnderlyingObject(Value *V, const DataLayout &DL,
339  unsigned MaxLookup = 6);
340  inline const Value *GetUnderlyingObject(const Value *V, const DataLayout &DL,
341  unsigned MaxLookup = 6) {
342  return GetUnderlyingObject(const_cast<Value *>(V), DL, MaxLookup);
343  }
344 
345  /// This method is similar to GetUnderlyingObject except that it can
346  /// look through phi and select instructions and return multiple objects.
347  ///
348  /// If LoopInfo is passed, loop phis are further analyzed. If a pointer
349  /// accesses different objects in each iteration, we don't look through the
350  /// phi node. E.g. consider this loop nest:
351  ///
352  /// int **A;
353  /// for (i)
354  /// for (j) {
355  /// A[i][j] = A[i-1][j] * B[j]
356  /// }
357  ///
358  /// This is transformed by Load-PRE to stash away A[i] for the next iteration
359  /// of the outer loop:
360  ///
361  /// Curr = A[0]; // Prev_0
362  /// for (i: 1..N) {
363  /// Prev = Curr; // Prev = PHI (Prev_0, Curr)
364  /// Curr = A[i];
365  /// for (j: 0..N) {
366  /// Curr[j] = Prev[j] * B[j]
367  /// }
368  /// }
369  ///
370  /// Since A[i] and A[i-1] are independent pointers, getUnderlyingObjects
371  /// should not assume that Curr and Prev share the same underlying object thus
372  /// it shouldn't look through the phi above.
373  void GetUnderlyingObjects(const Value *V,
375  const DataLayout &DL, LoopInfo *LI = nullptr,
376  unsigned MaxLookup = 6);
377 
378  /// This is a wrapper around GetUnderlyingObjects and adds support for basic
379  /// ptrtoint+arithmetic+inttoptr sequences.
381  SmallVectorImpl<Value *> &Objects,
382  const DataLayout &DL);
383 
384  /// Return true if the only users of this pointer are lifetime markers.
385  bool onlyUsedByLifetimeMarkers(const Value *V);
386 
387  /// Return true if speculation of the given load must be suppressed to avoid
388  /// ordering or interfering with an active sanitizer. If not suppressed,
389  /// dereferenceability and alignment must be proven separately. Note: This
390  /// is only needed for raw reasoning; if you use the interface below
391  /// (isSafeToSpeculativelyExecute), this is handled internally.
392  bool mustSuppressSpeculation(const LoadInst &LI);
393 
394  /// Return true if the instruction does not have any effects besides
395  /// calculating the result and does not have undefined behavior.
396  ///
397  /// This method never returns true for an instruction that returns true for
398  /// mayHaveSideEffects; however, this method also does some other checks in
399  /// addition. It checks for undefined behavior, like dividing by zero or
400  /// loading from an invalid pointer (but not for undefined results, like a
401  /// shift with a shift amount larger than the width of the result). It checks
402  /// for malloc and alloca because speculatively executing them might cause a
403  /// memory leak. It also returns false for instructions related to control
404  /// flow, specifically terminators and PHI nodes.
405  ///
406  /// If the CtxI is specified this method performs context-sensitive analysis
407  /// and returns true if it is safe to execute the instruction immediately
408  /// before the CtxI.
409  ///
410  /// If the CtxI is NOT specified this method only looks at the instruction
411  /// itself and its operands, so if this method returns true, it is safe to
412  /// move the instruction as long as the correct dominance relationships for
413  /// the operands and users hold.
414  ///
415  /// This method can return true for instructions that read memory;
416  /// for such instructions, moving them may change the resulting value.
417  bool isSafeToSpeculativelyExecute(const Value *V,
418  const Instruction *CtxI = nullptr,
419  const DominatorTree *DT = nullptr);
420 
421  /// Returns true if the result or effects of the given instructions \p I
422  /// depend on or influence global memory.
423  /// Memory dependence arises for example if the instruction reads from
424  /// memory or may produce effects or undefined behaviour. Memory dependent
425  /// instructions generally cannot be reorderd with respect to other memory
426  /// dependent instructions or moved into non-dominated basic blocks.
427  /// Instructions which just compute a value based on the values of their
428  /// operands are not memory dependent.
429  bool mayBeMemoryDependent(const Instruction &I);
430 
431  /// Return true if it is an intrinsic that cannot be speculated but also
432  /// cannot trap.
433  bool isAssumeLikeIntrinsic(const Instruction *I);
434 
435  /// Return true if it is valid to use the assumptions provided by an
436  /// assume intrinsic, I, at the point in the control-flow identified by the
437  /// context instruction, CxtI.
438  bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI,
439  const DominatorTree *DT = nullptr);
440 
441  enum class OverflowResult {
442  /// Always overflows in the direction of signed/unsigned min value.
444  /// Always overflows in the direction of signed/unsigned max value.
446  /// May or may not overflow.
447  MayOverflow,
448  /// Never overflows.
450  };
451 
453  const Value *RHS,
454  const DataLayout &DL,
455  AssumptionCache *AC,
456  const Instruction *CxtI,
457  const DominatorTree *DT,
458  bool UseInstrInfo = true);
459  OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS,
460  const DataLayout &DL,
461  AssumptionCache *AC,
462  const Instruction *CxtI,
463  const DominatorTree *DT,
464  bool UseInstrInfo = true);
466  const Value *RHS,
467  const DataLayout &DL,
468  AssumptionCache *AC,
469  const Instruction *CxtI,
470  const DominatorTree *DT,
471  bool UseInstrInfo = true);
472  OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS,
473  const DataLayout &DL,
474  AssumptionCache *AC = nullptr,
475  const Instruction *CxtI = nullptr,
476  const DominatorTree *DT = nullptr);
477  /// This version also leverages the sign bit of Add if known.
479  const DataLayout &DL,
480  AssumptionCache *AC = nullptr,
481  const Instruction *CxtI = nullptr,
482  const DominatorTree *DT = nullptr);
484  const DataLayout &DL,
485  AssumptionCache *AC,
486  const Instruction *CxtI,
487  const DominatorTree *DT);
488  OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS,
489  const DataLayout &DL,
490  AssumptionCache *AC,
491  const Instruction *CxtI,
492  const DominatorTree *DT);
493 
494  /// Returns true if the arithmetic part of the \p WO 's result is
495  /// used only along the paths control dependent on the computation
496  /// not overflowing, \p WO being an <op>.with.overflow intrinsic.
498  const DominatorTree &DT);
499 
500 
501  /// Determine the possible constant range of an integer or vector of integer
502  /// value. This is intended as a cheap, non-recursive check.
503  ConstantRange computeConstantRange(const Value *V, bool UseInstrInfo = true);
504 
505  /// Return true if this function can prove that the instruction I will
506  /// always transfer execution to one of its successors (including the next
507  /// instruction that follows within a basic block). E.g. this is not
508  /// guaranteed for function calls that could loop infinitely.
509  ///
510  /// In other words, this function returns false for instructions that may
511  /// transfer execution or fail to transfer execution in a way that is not
512  /// captured in the CFG nor in the sequence of instructions within a basic
513  /// block.
514  ///
515  /// Undefined behavior is assumed not to happen, so e.g. division is
516  /// guaranteed to transfer execution to the following instruction even
517  /// though division by zero might cause undefined behavior.
519 
520  /// Returns true if this block does not contain a potential implicit exit.
521  /// This is equivelent to saying that all instructions within the basic block
522  /// are guaranteed to transfer execution to their successor within the basic
523  /// block. This has the same assumptions w.r.t. undefined behavior as the
524  /// instruction variant of this function.
526 
527  /// Return true if this function can prove that the instruction I
528  /// is executed for every iteration of the loop L.
529  ///
530  /// Note that this currently only considers the loop header.
532  const Loop *L);
533 
534  /// Return true if this function can prove that I is guaranteed to yield
535  /// full-poison (all bits poison) if at least one of its operands are
536  /// full-poison (all bits poison).
537  ///
538  /// The exact rules for how poison propagates through instructions have
539  /// not been settled as of 2015-07-10, so this function is conservative
540  /// and only considers poison to be propagated in uncontroversial
541  /// cases. There is no attempt to track values that may be only partially
542  /// poison.
543  bool propagatesFullPoison(const Instruction *I);
544 
545  /// Return either nullptr or an operand of I such that I will trigger
546  /// undefined behavior if I is executed and that operand has a full-poison
547  /// value (all bits poison).
549 
550  /// Return true if the given instruction must trigger undefined behavior.
551  /// when I is executed with any operands which appear in KnownPoison holding
552  /// a full-poison value at the point of execution.
553  bool mustTriggerUB(const Instruction *I,
554  const SmallSet<const Value *, 16>& KnownPoison);
555 
556  /// Return true if this function can prove that if PoisonI is executed
557  /// and yields a full-poison value (all bits poison), then that will
558  /// trigger undefined behavior.
559  ///
560  /// Note that this currently only considers the basic block that is
561  /// the parent of I.
562  bool programUndefinedIfFullPoison(const Instruction *PoisonI);
563 
564  /// Specific patterns of select instructions we can match.
567  SPF_SMIN, /// Signed minimum
568  SPF_UMIN, /// Unsigned minimum
569  SPF_SMAX, /// Signed maximum
570  SPF_UMAX, /// Unsigned maximum
571  SPF_FMINNUM, /// Floating point minnum
572  SPF_FMAXNUM, /// Floating point maxnum
573  SPF_ABS, /// Absolute value
574  SPF_NABS /// Negated absolute value
575  };
576 
577  /// Behavior when a floating point min/max is given one NaN and one
578  /// non-NaN as input.
580  SPNB_NA = 0, /// NaN behavior not applicable.
581  SPNB_RETURNS_NAN, /// Given one NaN input, returns the NaN.
582  SPNB_RETURNS_OTHER, /// Given one NaN input, returns the non-NaN.
583  SPNB_RETURNS_ANY /// Given one NaN input, can return either (or
584  /// it has been determined that no operands can
585  /// be NaN).
586  };
587 
590  SelectPatternNaNBehavior NaNBehavior; /// Only applicable if Flavor is
591  /// SPF_FMINNUM or SPF_FMAXNUM.
592  bool Ordered; /// When implementing this min/max pattern as
593  /// fcmp; select, does the fcmp have to be
594  /// ordered?
595 
596  /// Return true if \p SPF is a min or a max pattern.
597  static bool isMinOrMax(SelectPatternFlavor SPF) {
598  return SPF != SPF_UNKNOWN && SPF != SPF_ABS && SPF != SPF_NABS;
599  }
600  };
601 
602  /// Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind
603  /// and providing the out parameter results if we successfully match.
604  ///
605  /// For ABS/NABS, LHS will be set to the input to the abs idiom. RHS will be
606  /// the negation instruction from the idiom.
607  ///
608  /// If CastOp is not nullptr, also match MIN/MAX idioms where the type does
609  /// not match that of the original select. If this is the case, the cast
610  /// operation (one of Trunc,SExt,Zext) that must be done to transform the
611  /// type of LHS and RHS into the type of V is returned in CastOp.
612  ///
613  /// For example:
614  /// %1 = icmp slt i32 %a, i32 4
615  /// %2 = sext i32 %a to i64
616  /// %3 = select i1 %1, i64 %2, i64 4
617  ///
618  /// -> LHS = %a, RHS = i32 4, *CastOp = Instruction::SExt
619  ///
621  Instruction::CastOps *CastOp = nullptr,
622  unsigned Depth = 0);
623 
624  inline SelectPatternResult
625  matchSelectPattern(const Value *V, const Value *&LHS, const Value *&RHS) {
626  Value *L = const_cast<Value *>(LHS);
627  Value *R = const_cast<Value *>(RHS);
628  auto Result = matchSelectPattern(const_cast<Value *>(V), L, R);
629  LHS = L;
630  RHS = R;
631  return Result;
632  }
633 
634  /// Determine the pattern that a select with the given compare as its
635  /// predicate and given values as its true/false operands would match.
637  CmpInst *CmpI, Value *TrueVal, Value *FalseVal, Value *&LHS, Value *&RHS,
638  Instruction::CastOps *CastOp = nullptr, unsigned Depth = 0);
639 
640  /// Return the canonical comparison predicate for the specified
641  /// minimum/maximum flavor.
643  bool Ordered = false);
644 
645  /// Return the inverse minimum/maximum flavor of the specified flavor.
646  /// For example, signed minimum is the inverse of signed maximum.
648 
649  /// Return the canonical inverse comparison predicate for the specified
650  /// minimum/maximum flavor.
652 
653  /// Return true if RHS is known to be implied true by LHS. Return false if
654  /// RHS is known to be implied false by LHS. Otherwise, return None if no
655  /// implication can be made.
656  /// A & B must be i1 (boolean) values or a vector of such values. Note that
657  /// the truth table for implication is the same as <=u on i1 values (but not
658  /// <=s!). The truth table for both is:
659  /// | T | F (B)
660  /// T | T | F
661  /// F | T | T
662  /// (A)
663  Optional<bool> isImpliedCondition(const Value *LHS, const Value *RHS,
664  const DataLayout &DL, bool LHSIsTrue = true,
665  unsigned Depth = 0);
666 
667  /// Return the boolean condition value in the context of the given instruction
668  /// if it is known based on dominating conditions.
670  const Instruction *ContextI,
671  const DataLayout &DL);
672 
673  /// If Ptr1 is provably equal to Ptr2 plus a constant offset, return that
674  /// offset. For example, Ptr1 might be &A[42], and Ptr2 might be &A[40]. In
675  /// this case offset would be -8.
676  Optional<int64_t> isPointerOffset(const Value *Ptr1, const Value *Ptr2,
677  const DataLayout &DL);
678 } // end namespace llvm
679 
680 #endif // LLVM_ANALYSIS_VALUETRACKING_H
const Value * getGuaranteedNonFullPoisonOp(const Instruction *I)
Return either nullptr or an operand of I such that I will trigger undefined behavior if I is executed...
bool isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the given value is known be positive (i.e.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:112
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:722
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Value * GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, const DataLayout &DL, bool AllowNonInbounds=true)
Analyze the specified pointer to see if it can be expressed as a base pointer plus a constant offset...
bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI)
Unsigned minimum.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Represents an op.with.overflow intrinsic.
Optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
A cache of @llvm.assume calls within a function.
Always overflows in the direction of signed/unsigned min value.
bool mustSuppressSpeculation(const LoadInst &LI)
Return true if speculation of the given load must be suppressed to avoid ordering or interfering with...
bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, const DominatorTree *DT=nullptr)
Return true if it is valid to use the assumptions provided by an assume intrinsic, I, at the point in the control-flow identified by the context instruction, CxtI.
SelectPatternFlavor getInverseMinMaxFlavor(SelectPatternFlavor SPF)
Return the inverse minimum/maximum flavor of the specified flavor.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
An instruction for reading from memory.
Definition: Instructions.h:169
ConstantRange computeConstantRange(const Value *V, bool UseInstrInfo=true)
Determine the possible constant range of an integer or vector of integer value.
Hexagon Common GEP
bool isGEPBasedOnPointerToString(const GEPOperator *GEP, unsigned CharSize=8)
Returns true if the GEP is based on a pointer to a string (array of.
uint64_t Offset
Slice starts at this Offset.
bool Ordered
Only applicable if Flavor is SPF_FMINNUM or SPF_FMAXNUM.
bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(const CallBase *Call, bool MustPreserveNullness)
{launder,strip}.invariant.group returns pointer that aliases its argument, and it only captures point...
bool propagatesFullPoison(const Instruction *I)
Return true if this function can prove that I is guaranteed to yield full-poison (all bits poison) if...
Signed maximum.
Intrinsic::ID getIntrinsicForCallSite(ImmutableCallSite ICS, const TargetLibraryInfo *TLI)
Map a call instruction to an intrinsic ID.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, bool OrZero=false, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to have exactly one bit set when defined. ...
Absolute value.
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
NaN behavior not applicable.
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if &#39;V & Mask&#39; is known to be zero.
bool programUndefinedIfFullPoison(const Instruction *PoisonI)
Return true if this function can prove that if PoisonI is executed and yields a full-poison value (al...
uint64_t operator[](unsigned I) const
Convenience accessor for elements in the slice.
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1583
bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO, const DominatorTree &DT)
Returns true if the arithmetic part of the WO &#39;s result is used only along the paths control dependen...
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
const ConstantDataArray * Array
ConstantDataArray pointer.
May or may not overflow.
SelectPatternResult matchDecomposedSelectPattern(CmpInst *CmpI, Value *TrueVal, Value *FalseVal, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Determine the pattern that a select with the given compare as its predicate and given values as its t...
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the give value is known to be non-negative.
uint64_t GetStringLength(const Value *V, unsigned CharSize=8)
If we can compute the length of the string pointed to by the specified pointer, return &#39;len+1&#39;...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
bool CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI, unsigned Depth=0)
Return true if we can prove that the specified FP value is never equal to -0.0.
bool getConstantDataArrayInfo(const Value *V, ConstantDataArraySlice &Slice, unsigned ElementSize, uint64_t Offset=0)
Returns true if the value V is a pointer into a ConstantDataArray.
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return the number of times the sign bit of the register is replicated into the other bits...
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
void GetUnderlyingObjects(const Value *V, SmallVectorImpl< const Value *> &Objects, const DataLayout &DL, LoopInfo *LI=nullptr, unsigned MaxLookup=6)
This method is similar to GetUnderlyingObject except that it can look through phi and select instruct...
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW=false)
Return true if the two given values are negation.
An array constant whose element type is a simple 1/2/4/8-byte integer or float/double, and whose elements are just simple data values (i.e.
Definition: Constants.h:689
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool onlyUsedByLifetimeMarkers(const Value *V)
Return true if the only users of this pointer are lifetime markers.
bool getUnderlyingObjectsForCodeGen(const Value *V, SmallVectorImpl< Value *> &Objects, const DataLayout &DL)
This is a wrapper around GetUnderlyingObjects and adds support for basic ptrtoint+arithmetic+inttoptr...
bool mustTriggerUB(const Instruction *I, const SmallSet< const Value *, 16 > &KnownPoison)
Return true if the given instruction must trigger undefined behavior.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:732
CmpInst::Predicate getMinMaxPred(SelectPatternFlavor SPF, bool Ordered=false)
Return the canonical comparison predicate for the specified minimum/maximum flavor.
SelectPatternNaNBehavior
Behavior when a floating point min/max is given one NaN and one non-NaN as input. ...
unsigned getIndexTypeSizeInBits(Type *Ty) const
Layout size of the index used in GEP calculation.
Definition: DataLayout.cpp:687
Represents offset+length into a ConstantDataArray.
CmpInst::Predicate getInverseMinMaxPred(SelectPatternFlavor SPF)
Return the canonical inverse comparison predicate for the specified minimum/maximum flavor...
bool isAssumeLikeIntrinsic(const Instruction *I)
Return true if it is an intrinsic that cannot be speculated but also cannot trap. ...
Value * GetUnderlyingObject(Value *V, const DataLayout &DL, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value...
Value * FindInsertedValue(Value *V, ArrayRef< unsigned > idx_range, Instruction *InsertBefore=nullptr)
Given an aggregrate and an sequence of indices, see if the scalar value indexed is already around as ...
Floating point maxnum.
Value * isBytewiseValue(Value *V, const DataLayout &DL)
If the specified value can be set by repeating the same byte in memory, return the i8 value that it i...
Given one NaN input, returns the non-NaN.
const Value * getArgumentAliasingToReturnedPointer(const CallBase *Call, bool MustPreserveNullness)
This function returns call pointer argument that is considered the same by aliasing rules...
SelectPatternFlavor Flavor
Unsigned maximum.
uint64_t getElementAsInteger(unsigned i) const
If this is a sequential container of integers (of any size), return the specified element in the low ...
Definition: Constants.cpp:2692
uint64_t Length
Length of the slice.
SelectPatternFlavor
Specific patterns of select instructions we can match.
This class represents a range of values.
Definition: ConstantRange.h:47
Floating point minnum.
SelectPatternNaNBehavior NaNBehavior
void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, KnownBits &Known)
Compute known bits from the range metadata.
Optional< int64_t > isPointerOffset(const Value *Ptr1, const Value *Ptr2, const DataLayout &DL)
If Ptr1 is provably equal to Ptr2 plus a constant offset, return that offset.
Class for arbitrary precision integers.
Definition: APInt.h:69
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds) const
Accumulate the constant offset this value has compared to a base pointer.
Definition: Value.cpp:550
Always overflows in the direction of signed/unsigned max value.
bool mayBeMemoryDependent(const Instruction &I)
Returns true if the result or effects of the given instructions I depend on or influence global memor...
OverflowResult
bool isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the given value is known be negative (i.e.
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given values are known to be non-equal when defined.
#define I(x, y, z)
Definition: MD5.cpp:58
bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if LHS and RHS have no common bits set.
bool SignBitMustBeZero(const Value *V, const TargetLibraryInfo *TLI)
Return true if we can prove that the specified FP value&#39;s sign bit is 0.
bool ComputeMultiple(Value *V, unsigned Base, Value *&Multiple, bool LookThroughSExt=false, unsigned Depth=0)
This function computes the integer multiple of Base that equals V.
bool isGuaranteedToExecuteForEveryIteration(const Instruction *I, const Loop *L)
Return true if this function can prove that the instruction I is executed for every iteration of the ...
bool isKnownNeverNaN(const Value *V, const TargetLibraryInfo *TLI, unsigned Depth=0)
Return true if the floating-point scalar value is not a NaN or if the floating-point vector value has...
Signed minimum.
Optional< bool > isImpliedCondition(const Value *LHS, const Value *RHS, const DataLayout &DL, bool LHSIsTrue=true, unsigned Depth=0)
Return true if RHS is known to be implied true by LHS.
bool getConstantStringInfo(const Value *V, StringRef &Str, uint64_t Offset=0, bool TrimAtNul=true)
This function computes the length of a null-terminated C string pointed to by V.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Given one NaN input, returns the NaN.
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
LLVM Value Representation.
Definition: Value.h:74
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
void move(uint64_t Delta)
Moves the Offset and adjusts Length accordingly.
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
bool CannotBeOrderedLessThanZero(const Value *V, const TargetLibraryInfo *TLI)
Return true if we can prove that the specified FP value is either NaN or never less than -0...
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)