LLVM  6.0.0svn
ValueTracking.h
Go to the documentation of this file.
1 //===- llvm/Analysis/ValueTracking.h - Walk computations --------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains routines that help analyze properties that chains of
11 // computations have.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_ANALYSIS_VALUETRACKING_H
16 #define LLVM_ANALYSIS_VALUETRACKING_H
17 
18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/Optional.h"
20 #include "llvm/IR/CallSite.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/Instruction.h"
23 #include "llvm/IR/Intrinsics.h"
24 #include <cassert>
25 #include <cstdint>
26 
27 namespace llvm {
28 
29 class AddOperator;
30 class APInt;
31 class AssumptionCache;
32 class DataLayout;
33 class DominatorTree;
34 class GEPOperator;
35 class IntrinsicInst;
36 struct KnownBits;
37 class Loop;
38 class LoopInfo;
39 class MDNode;
40 class OptimizationRemarkEmitter;
41 class StringRef;
42 class TargetLibraryInfo;
43 class Value;
44 
45  /// Determine which bits of V are known to be either zero or one and return
46  /// them in the KnownZero/KnownOne bit sets.
47  ///
48  /// This function is defined on values with integer type, values with pointer
49  /// type, and vectors of integers. In the case
50  /// where V is a vector, the known zero and known one values are the
51  /// same width as the vector element, and the bit is set only if it is true
52  /// for all of the elements in the vector.
53  void computeKnownBits(const Value *V, KnownBits &Known,
54  const DataLayout &DL, unsigned Depth = 0,
55  AssumptionCache *AC = nullptr,
56  const Instruction *CxtI = nullptr,
57  const DominatorTree *DT = nullptr,
58  OptimizationRemarkEmitter *ORE = nullptr);
59 
60  /// Returns the known bits rather than passing by reference.
61  KnownBits computeKnownBits(const Value *V, const DataLayout &DL,
62  unsigned Depth = 0, AssumptionCache *AC = nullptr,
63  const Instruction *CxtI = nullptr,
64  const DominatorTree *DT = nullptr,
65  OptimizationRemarkEmitter *ORE = nullptr);
66 
67  /// Compute known bits from the range metadata.
68  /// \p KnownZero the set of bits that are known to be zero
69  /// \p KnownOne the set of bits that are known to be one
70  void computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
71  KnownBits &Known);
72 
73  /// Return true if LHS and RHS have no common bits set.
74  bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS,
75  const DataLayout &DL,
76  AssumptionCache *AC = nullptr,
77  const Instruction *CxtI = nullptr,
78  const DominatorTree *DT = nullptr);
79 
80  /// Return true if the given value is known to have exactly one bit set when
81  /// defined. For vectors return true if every element is known to be a power
82  /// of two when defined. Supports values with integer or pointer type and
83  /// vectors of integers. If 'OrZero' is set, then return true if the given
84  /// value is either a power of two or zero.
85  bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL,
86  bool OrZero = false, unsigned Depth = 0,
87  AssumptionCache *AC = nullptr,
88  const Instruction *CxtI = nullptr,
89  const DominatorTree *DT = nullptr);
90 
91  bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI);
92 
93  /// Return true if the given value is known to be non-zero when defined. For
94  /// vectors, return true if every element is known to be non-zero when
95  /// defined. For pointers, if the context instruction and dominator tree are
96  /// specified, perform context-sensitive analysis and return true if the
97  /// pointer couldn't possibly be null at the specified instruction.
98  /// Supports values with integer or pointer type and vectors of integers.
99  bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth = 0,
100  AssumptionCache *AC = nullptr,
101  const Instruction *CxtI = nullptr,
102  const DominatorTree *DT = nullptr);
103 
104  /// Returns true if the give value is known to be non-negative.
105  bool isKnownNonNegative(const Value *V, const DataLayout &DL,
106  unsigned Depth = 0,
107  AssumptionCache *AC = nullptr,
108  const Instruction *CxtI = nullptr,
109  const DominatorTree *DT = nullptr);
110 
111  /// Returns true if the given value is known be positive (i.e. non-negative
112  /// and non-zero).
113  bool isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth = 0,
114  AssumptionCache *AC = nullptr,
115  const Instruction *CxtI = nullptr,
116  const DominatorTree *DT = nullptr);
117 
118  /// Returns true if the given value is known be negative (i.e. non-positive
119  /// and non-zero).
120  bool isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth = 0,
121  AssumptionCache *AC = nullptr,
122  const Instruction *CxtI = nullptr,
123  const DominatorTree *DT = nullptr);
124 
125  /// Return true if the given values are known to be non-equal when defined.
126  /// Supports scalar integer types only.
127  bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL,
128  AssumptionCache *AC = nullptr,
129  const Instruction *CxtI = nullptr,
130  const DominatorTree *DT = nullptr);
131 
132  /// Return true if 'V & Mask' is known to be zero. We use this predicate to
133  /// simplify operations downstream. Mask is known to be zero for bits that V
134  /// cannot have.
135  ///
136  /// This function is defined on values with integer type, values with pointer
137  /// type, and vectors of integers. In the case
138  /// where V is a vector, the mask, known zero, and known one values are the
139  /// same width as the vector element, and the bit is set only if it is true
140  /// for all of the elements in the vector.
141  bool MaskedValueIsZero(const Value *V, const APInt &Mask,
142  const DataLayout &DL,
143  unsigned Depth = 0, AssumptionCache *AC = nullptr,
144  const Instruction *CxtI = nullptr,
145  const DominatorTree *DT = nullptr);
146 
147  /// Return the number of times the sign bit of the register is replicated into
148  /// the other bits. We know that at least 1 bit is always equal to the sign
149  /// bit (itself), but other cases can give us information. For example,
150  /// immediately after an "ashr X, 2", we know that the top 3 bits are all
151  /// equal to each other, so we return 3. For vectors, return the number of
152  /// sign bits for the vector element with the mininum number of known sign
153  /// bits.
154  unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL,
155  unsigned Depth = 0, AssumptionCache *AC = nullptr,
156  const Instruction *CxtI = nullptr,
157  const DominatorTree *DT = nullptr);
158 
159  /// This function computes the integer multiple of Base that equals V. If
160  /// successful, it returns true and returns the multiple in Multiple. If
161  /// unsuccessful, it returns false. Also, if V can be simplified to an
162  /// integer, then the simplified V is returned in Val. Look through sext only
163  /// if LookThroughSExt=true.
164  bool ComputeMultiple(Value *V, unsigned Base, Value *&Multiple,
165  bool LookThroughSExt = false,
166  unsigned Depth = 0);
167 
168  /// Map a call instruction to an intrinsic ID. Libcalls which have equivalent
169  /// intrinsics are treated as-if they were intrinsics.
170  Intrinsic::ID getIntrinsicForCallSite(ImmutableCallSite ICS,
171  const TargetLibraryInfo *TLI);
172 
173  /// Return true if we can prove that the specified FP value is never equal to
174  /// -0.0.
175  bool CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI,
176  unsigned Depth = 0);
177 
178  /// Return true if we can prove that the specified FP value is either NaN or
179  /// never less than -0.0.
180  ///
181  /// NaN --> true
182  /// +0 --> true
183  /// -0 --> true
184  /// x > +0 --> true
185  /// x < -0 --> false
186  bool CannotBeOrderedLessThanZero(const Value *V, const TargetLibraryInfo *TLI);
187 
188  /// Return true if the floating-point scalar value is not a NaN or if the
189  /// floating-point vector value has no NaN elements. Return false if a value
190  /// could ever be NaN.
191  bool isKnownNeverNaN(const Value *V);
192 
193  /// Return true if we can prove that the specified FP value's sign bit is 0.
194  ///
195  /// NaN --> true/false (depending on the NaN's sign bit)
196  /// +0 --> true
197  /// -0 --> false
198  /// x > +0 --> true
199  /// x < -0 --> false
200  bool SignBitMustBeZero(const Value *V, const TargetLibraryInfo *TLI);
201 
202  /// If the specified value can be set by repeating the same byte in memory,
203  /// return the i8 value that it is represented with. This is true for all i8
204  /// values obviously, but is also true for i32 0, i32 -1, i16 0xF0F0, double
205  /// 0.0 etc. If the value can't be handled with a repeated byte store (e.g.
206  /// i16 0x1234), return null.
207  Value *isBytewiseValue(Value *V);
208 
209  /// Given an aggregrate and an sequence of indices, see if the scalar value
210  /// indexed is already around as a register, for example if it were inserted
211  /// directly into the aggregrate.
212  ///
213  /// If InsertBefore is not null, this function will duplicate (modified)
214  /// insertvalues when a part of a nested struct is extracted.
215  Value *FindInsertedValue(Value *V,
216  ArrayRef<unsigned> idx_range,
217  Instruction *InsertBefore = nullptr);
218 
219  /// Analyze the specified pointer to see if it can be expressed as a base
220  /// pointer plus a constant offset. Return the base and offset to the caller.
221  Value *GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset,
222  const DataLayout &DL);
223  inline const Value *GetPointerBaseWithConstantOffset(const Value *Ptr,
224  int64_t &Offset,
225  const DataLayout &DL) {
226  return GetPointerBaseWithConstantOffset(const_cast<Value *>(Ptr), Offset,
227  DL);
228  }
229 
230  /// Returns true if the GEP is based on a pointer to a string (array of
231  // \p CharSize integers) and is indexing into this string.
233  unsigned CharSize = 8);
234 
235  /// Represents offset+length into a ConstantDataArray.
237  /// ConstantDataArray pointer. nullptr indicates a zeroinitializer (a valid
238  /// initializer, it just doesn't fit the ConstantDataArray interface).
240 
241  /// Slice starts at this Offset.
242  uint64_t Offset;
243 
244  /// Length of the slice.
245  uint64_t Length;
246 
247  /// Moves the Offset and adjusts Length accordingly.
248  void move(uint64_t Delta) {
249  assert(Delta < Length);
250  Offset += Delta;
251  Length -= Delta;
252  }
253 
254  /// Convenience accessor for elements in the slice.
255  uint64_t operator[](unsigned I) const {
256  return Array==nullptr ? 0 : Array->getElementAsInteger(I + Offset);
257  }
258  };
259 
260  /// Returns true if the value \p V is a pointer into a ConstantDataArray.
261  /// If successful \p Slice will point to a ConstantDataArray info object
262  /// with an appropriate offset.
264  unsigned ElementSize, uint64_t Offset = 0);
265 
266  /// This function computes the length of a null-terminated C string pointed to
267  /// by V. If successful, it returns true and returns the string in Str. If
268  /// unsuccessful, it returns false. This does not include the trailing null
269  /// character by default. If TrimAtNul is set to false, then this returns any
270  /// trailing null characters as well as any other characters that come after
271  /// it.
272  bool getConstantStringInfo(const Value *V, StringRef &Str,
273  uint64_t Offset = 0, bool TrimAtNul = true);
274 
275  /// If we can compute the length of the string pointed to by the specified
276  /// pointer, return 'len+1'. If we can't, return 0.
277  uint64_t GetStringLength(const Value *V, unsigned CharSize = 8);
278 
279  /// This method strips off any GEP address adjustments and pointer casts from
280  /// the specified value, returning the original object being addressed. Note
281  /// that the returned value has pointer type if the specified value does. If
282  /// the MaxLookup value is non-zero, it limits the number of instructions to
283  /// be stripped off.
284  Value *GetUnderlyingObject(Value *V, const DataLayout &DL,
285  unsigned MaxLookup = 6);
286  inline const Value *GetUnderlyingObject(const Value *V, const DataLayout &DL,
287  unsigned MaxLookup = 6) {
288  return GetUnderlyingObject(const_cast<Value *>(V), DL, MaxLookup);
289  }
290 
291  /// \brief This method is similar to GetUnderlyingObject except that it can
292  /// look through phi and select instructions and return multiple objects.
293  ///
294  /// If LoopInfo is passed, loop phis are further analyzed. If a pointer
295  /// accesses different objects in each iteration, we don't look through the
296  /// phi node. E.g. consider this loop nest:
297  ///
298  /// int **A;
299  /// for (i)
300  /// for (j) {
301  /// A[i][j] = A[i-1][j] * B[j]
302  /// }
303  ///
304  /// This is transformed by Load-PRE to stash away A[i] for the next iteration
305  /// of the outer loop:
306  ///
307  /// Curr = A[0]; // Prev_0
308  /// for (i: 1..N) {
309  /// Prev = Curr; // Prev = PHI (Prev_0, Curr)
310  /// Curr = A[i];
311  /// for (j: 0..N) {
312  /// Curr[j] = Prev[j] * B[j]
313  /// }
314  /// }
315  ///
316  /// Since A[i] and A[i-1] are independent pointers, getUnderlyingObjects
317  /// should not assume that Curr and Prev share the same underlying object thus
318  /// it shouldn't look through the phi above.
320  const DataLayout &DL, LoopInfo *LI = nullptr,
321  unsigned MaxLookup = 6);
322 
323  /// This is a wrapper around GetUnderlyingObjects and adds support for basic
324  /// ptrtoint+arithmetic+inttoptr sequences.
326  SmallVectorImpl<Value *> &Objects,
327  const DataLayout &DL);
328 
329  /// Return true if the only users of this pointer are lifetime markers.
330  bool onlyUsedByLifetimeMarkers(const Value *V);
331 
332  /// Return true if the instruction does not have any effects besides
333  /// calculating the result and does not have undefined behavior.
334  ///
335  /// This method never returns true for an instruction that returns true for
336  /// mayHaveSideEffects; however, this method also does some other checks in
337  /// addition. It checks for undefined behavior, like dividing by zero or
338  /// loading from an invalid pointer (but not for undefined results, like a
339  /// shift with a shift amount larger than the width of the result). It checks
340  /// for malloc and alloca because speculatively executing them might cause a
341  /// memory leak. It also returns false for instructions related to control
342  /// flow, specifically terminators and PHI nodes.
343  ///
344  /// If the CtxI is specified this method performs context-sensitive analysis
345  /// and returns true if it is safe to execute the instruction immediately
346  /// before the CtxI.
347  ///
348  /// If the CtxI is NOT specified this method only looks at the instruction
349  /// itself and its operands, so if this method returns true, it is safe to
350  /// move the instruction as long as the correct dominance relationships for
351  /// the operands and users hold.
352  ///
353  /// This method can return true for instructions that read memory;
354  /// for such instructions, moving them may change the resulting value.
355  bool isSafeToSpeculativelyExecute(const Value *V,
356  const Instruction *CtxI = nullptr,
357  const DominatorTree *DT = nullptr);
358 
359  /// Returns true if the result or effects of the given instructions \p I
360  /// depend on or influence global memory.
361  /// Memory dependence arises for example if the instruction reads from
362  /// memory or may produce effects or undefined behaviour. Memory dependent
363  /// instructions generally cannot be reorderd with respect to other memory
364  /// dependent instructions or moved into non-dominated basic blocks.
365  /// Instructions which just compute a value based on the values of their
366  /// operands are not memory dependent.
367  bool mayBeMemoryDependent(const Instruction &I);
368 
369  /// Return true if it is valid to use the assumptions provided by an
370  /// assume intrinsic, I, at the point in the control-flow identified by the
371  /// context instruction, CxtI.
372  bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI,
373  const DominatorTree *DT = nullptr);
374 
376 
378  const Value *RHS,
379  const DataLayout &DL,
380  AssumptionCache *AC,
381  const Instruction *CxtI,
382  const DominatorTree *DT);
384  const Value *RHS,
385  const DataLayout &DL,
386  AssumptionCache *AC,
387  const Instruction *CxtI,
388  const DominatorTree *DT);
389  OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS,
390  const DataLayout &DL,
391  AssumptionCache *AC = nullptr,
392  const Instruction *CxtI = nullptr,
393  const DominatorTree *DT = nullptr);
394  /// This version also leverages the sign bit of Add if known.
396  const DataLayout &DL,
397  AssumptionCache *AC = nullptr,
398  const Instruction *CxtI = nullptr,
399  const DominatorTree *DT = nullptr);
400 
401  /// Returns true if the arithmetic part of the \p II 's result is
402  /// used only along the paths control dependent on the computation
403  /// not overflowing, \p II being an <op>.with.overflow intrinsic.
405  const DominatorTree &DT);
406 
407  /// Return true if this function can prove that the instruction I will
408  /// always transfer execution to one of its successors (including the next
409  /// instruction that follows within a basic block). E.g. this is not
410  /// guaranteed for function calls that could loop infinitely.
411  ///
412  /// In other words, this function returns false for instructions that may
413  /// transfer execution or fail to transfer execution in a way that is not
414  /// captured in the CFG nor in the sequence of instructions within a basic
415  /// block.
416  ///
417  /// Undefined behavior is assumed not to happen, so e.g. division is
418  /// guaranteed to transfer execution to the following instruction even
419  /// though division by zero might cause undefined behavior.
421 
422  /// Return true if this function can prove that the instruction I
423  /// is executed for every iteration of the loop L.
424  ///
425  /// Note that this currently only considers the loop header.
427  const Loop *L);
428 
429  /// Return true if this function can prove that I is guaranteed to yield
430  /// full-poison (all bits poison) if at least one of its operands are
431  /// full-poison (all bits poison).
432  ///
433  /// The exact rules for how poison propagates through instructions have
434  /// not been settled as of 2015-07-10, so this function is conservative
435  /// and only considers poison to be propagated in uncontroversial
436  /// cases. There is no attempt to track values that may be only partially
437  /// poison.
438  bool propagatesFullPoison(const Instruction *I);
439 
440  /// Return either nullptr or an operand of I such that I will trigger
441  /// undefined behavior if I is executed and that operand has a full-poison
442  /// value (all bits poison).
444 
445  /// Return true if this function can prove that if PoisonI is executed
446  /// and yields a full-poison value (all bits poison), then that will
447  /// trigger undefined behavior.
448  ///
449  /// Note that this currently only considers the basic block that is
450  /// the parent of I.
451  bool programUndefinedIfFullPoison(const Instruction *PoisonI);
452 
453  /// \brief Specific patterns of select instructions we can match.
456  SPF_SMIN, /// Signed minimum
457  SPF_UMIN, /// Unsigned minimum
458  SPF_SMAX, /// Signed maximum
459  SPF_UMAX, /// Unsigned maximum
460  SPF_FMINNUM, /// Floating point minnum
461  SPF_FMAXNUM, /// Floating point maxnum
462  SPF_ABS, /// Absolute value
463  SPF_NABS /// Negated absolute value
464  };
465 
466  /// \brief Behavior when a floating point min/max is given one NaN and one
467  /// non-NaN as input.
469  SPNB_NA = 0, /// NaN behavior not applicable.
470  SPNB_RETURNS_NAN, /// Given one NaN input, returns the NaN.
471  SPNB_RETURNS_OTHER, /// Given one NaN input, returns the non-NaN.
472  SPNB_RETURNS_ANY /// Given one NaN input, can return either (or
473  /// it has been determined that no operands can
474  /// be NaN).
475  };
476 
479  SelectPatternNaNBehavior NaNBehavior; /// Only applicable if Flavor is
480  /// SPF_FMINNUM or SPF_FMAXNUM.
481  bool Ordered; /// When implementing this min/max pattern as
482  /// fcmp; select, does the fcmp have to be
483  /// ordered?
484 
485  /// \brief Return true if \p SPF is a min or a max pattern.
486  static bool isMinOrMax(SelectPatternFlavor SPF) {
487  return !(SPF == SPF_UNKNOWN || SPF == SPF_ABS || SPF == SPF_NABS);
488  }
489  };
490 
491  /// Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind
492  /// and providing the out parameter results if we successfully match.
493  ///
494  /// If CastOp is not nullptr, also match MIN/MAX idioms where the type does
495  /// not match that of the original select. If this is the case, the cast
496  /// operation (one of Trunc,SExt,Zext) that must be done to transform the
497  /// type of LHS and RHS into the type of V is returned in CastOp.
498  ///
499  /// For example:
500  /// %1 = icmp slt i32 %a, i32 4
501  /// %2 = sext i32 %a to i64
502  /// %3 = select i1 %1, i64 %2, i64 4
503  ///
504  /// -> LHS = %a, RHS = i32 4, *CastOp = Instruction::SExt
505  ///
507  Instruction::CastOps *CastOp = nullptr);
508  inline SelectPatternResult
509  matchSelectPattern(const Value *V, const Value *&LHS, const Value *&RHS,
510  Instruction::CastOps *CastOp = nullptr) {
511  Value *L = const_cast<Value*>(LHS);
512  Value *R = const_cast<Value*>(RHS);
513  auto Result = matchSelectPattern(const_cast<Value*>(V), L, R);
514  LHS = L;
515  RHS = R;
516  return Result;
517  }
518 
519  /// Return true if RHS is known to be implied true by LHS. Return false if
520  /// RHS is known to be implied false by LHS. Otherwise, return None if no
521  /// implication can be made.
522  /// A & B must be i1 (boolean) values or a vector of such values. Note that
523  /// the truth table for implication is the same as <=u on i1 values (but not
524  /// <=s!). The truth table for both is:
525  /// | T | F (B)
526  /// T | T | F
527  /// F | T | T
528  /// (A)
529  Optional<bool> isImpliedCondition(const Value *LHS, const Value *RHS,
530  const DataLayout &DL, bool LHSIsTrue = true,
531  unsigned Depth = 0);
532 } // end namespace llvm
533 
534 #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...
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
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)
Return true if the given value is known to have exactly one bit set when defined. ...
bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI)
Unsigned minimum.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Value * isBytewiseValue(Value *V)
If the specified value can be set by repeating the same byte in memory, return the i8 value that it i...
A cache of .assume calls within a function.
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.
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 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.
Absolute value.
NaN behavior not applicable.
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.
const ConstantDataArray * Array
ConstantDataArray pointer.
Value * GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, const DataLayout &DL)
Analyze the specified pointer to see if it can be expressed as a base pointer plus a constant offset...
bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return true if LHS and RHS have no common bits set.
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:140
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.
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
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.
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
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:681
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Returns true if the give value is known to be non-negative.
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 MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return true if &#39;V & Mask&#39; is known to be zero.
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 isOverflowIntrinsicNoWrap(const IntrinsicInst *II, const DominatorTree &DT)
Returns true if the arithmetic part of the II &#39;s result is used only along the paths control dependen...
SelectPatternNaNBehavior
Behavior when a floating point min/max is given one NaN and one non-NaN as input. ...
Represents offset+length into a ConstantDataArray.
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 ...
bool isKnownNeverNaN(const Value *V)
Return true if the floating-point scalar value is not a NaN or if the floating-point vector value has...
Floating point maxnum.
Given one NaN input, returns the non-NaN.
SelectPatternFlavor Flavor
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return the number of times the sign bit of the register is replicated into the other bits...
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:2564
uint64_t Length
Length of the slice.
SelectPatternFlavor
Specific patterns of select instructions we can match.
Floating point minnum.
SelectPatternNaNBehavior NaNBehavior
void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, KnownBits &Known)
Compute known bits from the range metadata.
bool isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Returns true if the given value is known be negative (i.e.
bool mayBeMemoryDependent(const Instruction &I)
Returns true if the result or effects of the given instructions I depend on or influence global memor...
OverflowResult
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:439
#define I(x, y, z)
Definition: MD5.cpp:58
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 ...
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
Signed minimum.
bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return true if the given values are known to be non-equal when defined.
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
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.
void GetUnderlyingObjects(Value *V, SmallVectorImpl< 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...
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:73
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:81
bool isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Returns true if the given value is known be positive (i.e.
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return true if the given value is known to be non-zero when defined.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
void move(uint64_t Delta)
Moves the Offset and adjusts Length accordingly.
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...
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)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44