LLVM  14.0.0git
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/Constants.h"
21 #include "llvm/IR/DataLayout.h"
22 #include "llvm/IR/InstrTypes.h"
23 #include "llvm/IR/Intrinsics.h"
24 #include "llvm/IR/Operator.h"
25 #include <cassert>
26 #include <cstdint>
27 
28 namespace llvm {
29 
30 class AddOperator;
31 class AllocaInst;
32 class APInt;
33 class AssumptionCache;
34 class DominatorTree;
35 class GEPOperator;
36 class IntrinsicInst;
37 class LoadInst;
38 class WithOverflowInst;
39 struct KnownBits;
40 class Loop;
41 class LoopInfo;
42 class MDNode;
43 class OptimizationRemarkEmitter;
44 class StringRef;
45 class TargetLibraryInfo;
46 class Value;
47 
48 constexpr unsigned MaxAnalysisRecursionDepth = 6;
49 
50  /// Determine which bits of V are known to be either zero or one and return
51  /// them in the KnownZero/KnownOne bit sets.
52  ///
53  /// This function is defined on values with integer type, values with pointer
54  /// type, and vectors of integers. In the case
55  /// where V is a vector, the known zero and known one values are the
56  /// same width as the vector element, and the bit is set only if it is true
57  /// for all of the elements in the vector.
58  void computeKnownBits(const Value *V, KnownBits &Known,
59  const DataLayout &DL, unsigned Depth = 0,
60  AssumptionCache *AC = nullptr,
61  const Instruction *CxtI = nullptr,
62  const DominatorTree *DT = nullptr,
63  OptimizationRemarkEmitter *ORE = nullptr,
64  bool UseInstrInfo = true);
65 
66  /// Determine which bits of V are known to be either zero or one and return
67  /// them in the KnownZero/KnownOne bit sets.
68  ///
69  /// This function is defined on values with integer type, values with pointer
70  /// type, and vectors of integers. In the case
71  /// where V is a vector, the known zero and known one values are the
72  /// same width as the vector element, and the bit is set only if it is true
73  /// for all of the demanded elements in the vector.
74  void computeKnownBits(const Value *V, const APInt &DemandedElts,
75  KnownBits &Known, const DataLayout &DL,
76  unsigned Depth = 0, AssumptionCache *AC = nullptr,
77  const Instruction *CxtI = nullptr,
78  const DominatorTree *DT = nullptr,
79  OptimizationRemarkEmitter *ORE = nullptr,
80  bool UseInstrInfo = true);
81 
82  /// Returns the known bits rather than passing by reference.
83  KnownBits computeKnownBits(const Value *V, const DataLayout &DL,
84  unsigned Depth = 0, AssumptionCache *AC = nullptr,
85  const Instruction *CxtI = nullptr,
86  const DominatorTree *DT = nullptr,
87  OptimizationRemarkEmitter *ORE = nullptr,
88  bool UseInstrInfo = true);
89 
90  /// Returns the known bits rather than passing by reference.
91  KnownBits computeKnownBits(const Value *V, const APInt &DemandedElts,
92  const DataLayout &DL, unsigned Depth = 0,
93  AssumptionCache *AC = nullptr,
94  const Instruction *CxtI = nullptr,
95  const DominatorTree *DT = nullptr,
96  OptimizationRemarkEmitter *ORE = nullptr,
97  bool UseInstrInfo = true);
98 
99  /// Compute known bits from the range metadata.
100  /// \p KnownZero the set of bits that are known to be zero
101  /// \p KnownOne the set of bits that are known to be one
102  void computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
103  KnownBits &Known);
104 
105  /// Return true if LHS and RHS have no common bits set.
106  bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS,
107  const DataLayout &DL,
108  AssumptionCache *AC = nullptr,
109  const Instruction *CxtI = nullptr,
110  const DominatorTree *DT = nullptr,
111  bool UseInstrInfo = true);
112 
113  /// Return true if the given value is known to have exactly one bit set when
114  /// defined. For vectors return true if every element is known to be a power
115  /// of two when defined. Supports values with integer or pointer type and
116  /// vectors of integers. If 'OrZero' is set, then return true if the given
117  /// value is either a power of two or zero.
118  bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL,
119  bool OrZero = false, unsigned Depth = 0,
120  AssumptionCache *AC = nullptr,
121  const Instruction *CxtI = nullptr,
122  const DominatorTree *DT = nullptr,
123  bool UseInstrInfo = true);
124 
126 
127  /// Return true if the given value is known to be non-zero when defined. For
128  /// vectors, return true if every element is known to be non-zero when
129  /// defined. For pointers, if the context instruction and dominator tree are
130  /// specified, perform context-sensitive analysis and return true if the
131  /// pointer couldn't possibly be null at the specified instruction.
132  /// Supports values with integer or pointer type and vectors of integers.
133  bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth = 0,
134  AssumptionCache *AC = nullptr,
135  const Instruction *CxtI = nullptr,
136  const DominatorTree *DT = nullptr,
137  bool UseInstrInfo = true);
138 
139  /// Return true if the two given values are negation.
140  /// Currently can recoginze Value pair:
141  /// 1: <X, Y> if X = sub (0, Y) or Y = sub (0, X)
142  /// 2: <X, Y> if X = sub (A, B) and Y = sub (B, A)
143  bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW = false);
144 
145  /// Returns true if the give value is known to be non-negative.
146  bool isKnownNonNegative(const Value *V, const DataLayout &DL,
147  unsigned Depth = 0,
148  AssumptionCache *AC = nullptr,
149  const Instruction *CxtI = nullptr,
150  const DominatorTree *DT = nullptr,
151  bool UseInstrInfo = true);
152 
153  /// Returns true if the given value is known be positive (i.e. non-negative
154  /// and non-zero).
155  bool isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth = 0,
156  AssumptionCache *AC = nullptr,
157  const Instruction *CxtI = nullptr,
158  const DominatorTree *DT = nullptr,
159  bool UseInstrInfo = true);
160 
161  /// Returns true if the given value is known be negative (i.e. non-positive
162  /// and non-zero).
163  bool isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth = 0,
164  AssumptionCache *AC = nullptr,
165  const Instruction *CxtI = nullptr,
166  const DominatorTree *DT = nullptr,
167  bool UseInstrInfo = true);
168 
169  /// Return true if the given values are known to be non-equal when defined.
170  /// Supports scalar integer types only.
171  bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL,
172  AssumptionCache *AC = nullptr,
173  const Instruction *CxtI = nullptr,
174  const DominatorTree *DT = nullptr,
175  bool UseInstrInfo = true);
176 
177  /// Return true if 'V & Mask' is known to be zero. We use this predicate to
178  /// simplify operations downstream. Mask is known to be zero for bits that V
179  /// cannot have.
180  ///
181  /// This function is defined on values with integer type, values with pointer
182  /// type, and vectors of integers. In the case
183  /// where V is a vector, the mask, known zero, and known one values are the
184  /// same width as the vector element, and the bit is set only if it is true
185  /// for all of the elements in the vector.
186  bool MaskedValueIsZero(const Value *V, const APInt &Mask,
187  const DataLayout &DL,
188  unsigned Depth = 0, AssumptionCache *AC = nullptr,
189  const Instruction *CxtI = nullptr,
190  const DominatorTree *DT = nullptr,
191  bool UseInstrInfo = true);
192 
193  /// Return the number of times the sign bit of the register is replicated into
194  /// the other bits. We know that at least 1 bit is always equal to the sign
195  /// bit (itself), but other cases can give us information. For example,
196  /// immediately after an "ashr X, 2", we know that the top 3 bits are all
197  /// equal to each other, so we return 3. For vectors, return the number of
198  /// sign bits for the vector element with the mininum number of known sign
199  /// bits.
200  unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL,
201  unsigned Depth = 0, AssumptionCache *AC = nullptr,
202  const Instruction *CxtI = nullptr,
203  const DominatorTree *DT = nullptr,
204  bool UseInstrInfo = true);
205 
206  /// This function computes the integer multiple of Base that equals V. If
207  /// successful, it returns true and returns the multiple in Multiple. If
208  /// unsuccessful, it returns false. Also, if V can be simplified to an
209  /// integer, then the simplified V is returned in Val. Look through sext only
210  /// if LookThroughSExt=true.
211  bool ComputeMultiple(Value *V, unsigned Base, Value *&Multiple,
212  bool LookThroughSExt = false,
213  unsigned Depth = 0);
214 
215  /// Map a call instruction to an intrinsic ID. Libcalls which have equivalent
216  /// intrinsics are treated as-if they were intrinsics.
218  const TargetLibraryInfo *TLI);
219 
220  /// Return true if we can prove that the specified FP value is never equal to
221  /// -0.0.
222  bool CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI,
223  unsigned Depth = 0);
224 
225  /// Return true if we can prove that the specified FP value is either NaN or
226  /// never less than -0.0.
227  ///
228  /// NaN --> true
229  /// +0 --> true
230  /// -0 --> true
231  /// x > +0 --> true
232  /// x < -0 --> false
233  bool CannotBeOrderedLessThanZero(const Value *V, const TargetLibraryInfo *TLI);
234 
235  /// Return true if the floating-point scalar value is not an infinity or if
236  /// the floating-point vector value has no infinities. Return false if a value
237  /// could ever be infinity.
238  bool isKnownNeverInfinity(const Value *V, const TargetLibraryInfo *TLI,
239  unsigned Depth = 0);
240 
241  /// Return true if the floating-point scalar value is not a NaN or if the
242  /// floating-point vector value has no NaN elements. Return false if a value
243  /// could ever be NaN.
244  bool isKnownNeverNaN(const Value *V, const TargetLibraryInfo *TLI,
245  unsigned Depth = 0);
246 
247  /// Return true if we can prove that the specified FP value's sign bit is 0.
248  ///
249  /// NaN --> true/false (depending on the NaN's sign bit)
250  /// +0 --> true
251  /// -0 --> false
252  /// x > +0 --> true
253  /// x < -0 --> false
254  bool SignBitMustBeZero(const Value *V, const TargetLibraryInfo *TLI);
255 
256  /// If the specified value can be set by repeating the same byte in memory,
257  /// return the i8 value that it is represented with. This is true for all i8
258  /// values obviously, but is also true for i32 0, i32 -1, i16 0xF0F0, double
259  /// 0.0 etc. If the value can't be handled with a repeated byte store (e.g.
260  /// i16 0x1234), return null. If the value is entirely undef and padding,
261  /// return undef.
262  Value *isBytewiseValue(Value *V, const DataLayout &DL);
263 
264  /// Given an aggregate and an sequence of indices, see if the scalar value
265  /// indexed is already around as a register, for example if it were inserted
266  /// directly into the aggregate.
267  ///
268  /// If InsertBefore is not null, this function will duplicate (modified)
269  /// insertvalues when a part of a nested struct is extracted.
271  ArrayRef<unsigned> idx_range,
272  Instruction *InsertBefore = nullptr);
273 
274  /// Analyze the specified pointer to see if it can be expressed as a base
275  /// pointer plus a constant offset. Return the base and offset to the caller.
276  ///
277  /// This is a wrapper around Value::stripAndAccumulateConstantOffsets that
278  /// creates and later unpacks the required APInt.
280  const DataLayout &DL,
281  bool AllowNonInbounds = true) {
282  APInt OffsetAPInt(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
283  Value *Base =
284  Ptr->stripAndAccumulateConstantOffsets(DL, OffsetAPInt, AllowNonInbounds);
285 
286  Offset = OffsetAPInt.getSExtValue();
287  return Base;
288  }
289  inline const Value *
291  const DataLayout &DL,
292  bool AllowNonInbounds = true) {
293  return GetPointerBaseWithConstantOffset(const_cast<Value *>(Ptr), Offset, DL,
294  AllowNonInbounds);
295  }
296 
297  /// Returns true if the GEP is based on a pointer to a string (array of
298  // \p CharSize integers) and is indexing into this string.
299  bool isGEPBasedOnPointerToString(const GEPOperator *GEP,
300  unsigned CharSize = 8);
301 
302  /// Represents offset+length into a ConstantDataArray.
304  /// ConstantDataArray pointer. nullptr indicates a zeroinitializer (a valid
305  /// initializer, it just doesn't fit the ConstantDataArray interface).
307 
308  /// Slice starts at this Offset.
310 
311  /// Length of the slice.
313 
314  /// Moves the Offset and adjusts Length accordingly.
315  void move(uint64_t Delta) {
316  assert(Delta < Length);
317  Offset += Delta;
318  Length -= Delta;
319  }
320 
321  /// Convenience accessor for elements in the slice.
322  uint64_t operator[](unsigned I) const {
323  return Array==nullptr ? 0 : Array->getElementAsInteger(I + Offset);
324  }
325  };
326 
327  /// Returns true if the value \p V is a pointer into a ConstantDataArray.
328  /// If successful \p Slice will point to a ConstantDataArray info object
329  /// with an appropriate offset.
330  bool getConstantDataArrayInfo(const Value *V, ConstantDataArraySlice &Slice,
331  unsigned ElementSize, uint64_t Offset = 0);
332 
333  /// This function computes the length of a null-terminated C string pointed to
334  /// by V. If successful, it returns true and returns the string in Str. If
335  /// unsuccessful, it returns false. This does not include the trailing null
336  /// character by default. If TrimAtNul is set to false, then this returns any
337  /// trailing null characters as well as any other characters that come after
338  /// it.
339  bool getConstantStringInfo(const Value *V, StringRef &Str,
340  uint64_t Offset = 0, bool TrimAtNul = true);
341 
342  /// If we can compute the length of the string pointed to by the specified
343  /// pointer, return 'len+1'. If we can't, return 0.
344  uint64_t GetStringLength(const Value *V, unsigned CharSize = 8);
345 
346  /// This function returns call pointer argument that is considered the same by
347  /// aliasing rules. You CAN'T use it to replace one value with another. If
348  /// \p MustPreserveNullness is true, the call must preserve the nullness of
349  /// the pointer.
350  const Value *getArgumentAliasingToReturnedPointer(const CallBase *Call,
351  bool MustPreserveNullness);
352  inline Value *
354  bool MustPreserveNullness) {
355  return const_cast<Value *>(getArgumentAliasingToReturnedPointer(
356  const_cast<const CallBase *>(Call), MustPreserveNullness));
357  }
358 
359  /// {launder,strip}.invariant.group returns pointer that aliases its argument,
360  /// and it only captures pointer by returning it.
361  /// These intrinsics are not marked as nocapture, because returning is
362  /// considered as capture. The arguments are not marked as returned neither,
363  /// because it would make it useless. If \p MustPreserveNullness is true,
364  /// the intrinsic must preserve the nullness of the pointer.
366  const CallBase *Call, bool MustPreserveNullness);
367 
368  /// This method strips off any GEP address adjustments and pointer casts from
369  /// the specified value, returning the original object being addressed. Note
370  /// that the returned value has pointer type if the specified value does. If
371  /// the MaxLookup value is non-zero, it limits the number of instructions to
372  /// be stripped off.
373  const Value *getUnderlyingObject(const Value *V, unsigned MaxLookup = 6);
374  inline Value *getUnderlyingObject(Value *V, unsigned MaxLookup = 6) {
375  // Force const to avoid infinite recursion.
376  const Value *VConst = V;
377  return const_cast<Value *>(getUnderlyingObject(VConst, MaxLookup));
378  }
379 
380  /// This method is similar to getUnderlyingObject except that it can
381  /// look through phi and select instructions and return multiple objects.
382  ///
383  /// If LoopInfo is passed, loop phis are further analyzed. If a pointer
384  /// accesses different objects in each iteration, we don't look through the
385  /// phi node. E.g. consider this loop nest:
386  ///
387  /// int **A;
388  /// for (i)
389  /// for (j) {
390  /// A[i][j] = A[i-1][j] * B[j]
391  /// }
392  ///
393  /// This is transformed by Load-PRE to stash away A[i] for the next iteration
394  /// of the outer loop:
395  ///
396  /// Curr = A[0]; // Prev_0
397  /// for (i: 1..N) {
398  /// Prev = Curr; // Prev = PHI (Prev_0, Curr)
399  /// Curr = A[i];
400  /// for (j: 0..N) {
401  /// Curr[j] = Prev[j] * B[j]
402  /// }
403  /// }
404  ///
405  /// Since A[i] and A[i-1] are independent pointers, getUnderlyingObjects
406  /// should not assume that Curr and Prev share the same underlying object thus
407  /// it shouldn't look through the phi above.
408  void getUnderlyingObjects(const Value *V,
409  SmallVectorImpl<const Value *> &Objects,
410  LoopInfo *LI = nullptr, unsigned MaxLookup = 6);
411 
412  /// This is a wrapper around getUnderlyingObjects and adds support for basic
413  /// ptrtoint+arithmetic+inttoptr sequences.
415  SmallVectorImpl<Value *> &Objects);
416 
417  /// Returns unique alloca where the value comes from, or nullptr.
418  /// If OffsetZero is true check that V points to the begining of the alloca.
419  AllocaInst *findAllocaForValue(Value *V, bool OffsetZero = false);
420  inline const AllocaInst *findAllocaForValue(const Value *V,
421  bool OffsetZero = false) {
422  return findAllocaForValue(const_cast<Value *>(V), OffsetZero);
423  }
424 
425  /// Return true if the only users of this pointer are lifetime markers.
426  bool onlyUsedByLifetimeMarkers(const Value *V);
427 
428  /// Return true if the only users of this pointer are lifetime markers or
429  /// droppable instructions.
431 
432  /// Return true if speculation of the given load must be suppressed to avoid
433  /// ordering or interfering with an active sanitizer. If not suppressed,
434  /// dereferenceability and alignment must be proven separately. Note: This
435  /// is only needed for raw reasoning; if you use the interface below
436  /// (isSafeToSpeculativelyExecute), this is handled internally.
437  bool mustSuppressSpeculation(const LoadInst &LI);
438 
439  /// Return true if the instruction does not have any effects besides
440  /// calculating the result and does not have undefined behavior.
441  ///
442  /// This method never returns true for an instruction that returns true for
443  /// mayHaveSideEffects; however, this method also does some other checks in
444  /// addition. It checks for undefined behavior, like dividing by zero or
445  /// loading from an invalid pointer (but not for undefined results, like a
446  /// shift with a shift amount larger than the width of the result). It checks
447  /// for malloc and alloca because speculatively executing them might cause a
448  /// memory leak. It also returns false for instructions related to control
449  /// flow, specifically terminators and PHI nodes.
450  ///
451  /// If the CtxI is specified this method performs context-sensitive analysis
452  /// and returns true if it is safe to execute the instruction immediately
453  /// before the CtxI.
454  ///
455  /// If the CtxI is NOT specified this method only looks at the instruction
456  /// itself and its operands, so if this method returns true, it is safe to
457  /// move the instruction as long as the correct dominance relationships for
458  /// the operands and users hold.
459  ///
460  /// This method can return true for instructions that read memory;
461  /// for such instructions, moving them may change the resulting value.
462  bool isSafeToSpeculativelyExecute(const Value *V,
463  const Instruction *CtxI = nullptr,
464  const DominatorTree *DT = nullptr,
465  const TargetLibraryInfo *TLI = nullptr);
466 
467  /// Returns true if the result or effects of the given instructions \p I
468  /// depend on or influence global memory.
469  /// Memory dependence arises for example if the instruction reads from
470  /// memory or may produce effects or undefined behaviour. Memory dependent
471  /// instructions generally cannot be reorderd with respect to other memory
472  /// dependent instructions or moved into non-dominated basic blocks.
473  /// Instructions which just compute a value based on the values of their
474  /// operands are not memory dependent.
475  bool mayBeMemoryDependent(const Instruction &I);
476 
477  /// Return true if it is an intrinsic that cannot be speculated but also
478  /// cannot trap.
479  bool isAssumeLikeIntrinsic(const Instruction *I);
480 
481  /// Return true if it is valid to use the assumptions provided by an
482  /// assume intrinsic, I, at the point in the control-flow identified by the
483  /// context instruction, CxtI.
484  bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI,
485  const DominatorTree *DT = nullptr);
486 
487  enum class OverflowResult {
488  /// Always overflows in the direction of signed/unsigned min value.
490  /// Always overflows in the direction of signed/unsigned max value.
492  /// May or may not overflow.
493  MayOverflow,
494  /// Never overflows.
496  };
497 
499  const Value *RHS,
500  const DataLayout &DL,
501  AssumptionCache *AC,
502  const Instruction *CxtI,
503  const DominatorTree *DT,
504  bool UseInstrInfo = true);
505  OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS,
506  const DataLayout &DL,
507  AssumptionCache *AC,
508  const Instruction *CxtI,
509  const DominatorTree *DT,
510  bool UseInstrInfo = true);
512  const Value *RHS,
513  const DataLayout &DL,
514  AssumptionCache *AC,
515  const Instruction *CxtI,
516  const DominatorTree *DT,
517  bool UseInstrInfo = true);
518  OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS,
519  const DataLayout &DL,
520  AssumptionCache *AC = nullptr,
521  const Instruction *CxtI = nullptr,
522  const DominatorTree *DT = nullptr);
523  /// This version also leverages the sign bit of Add if known.
524  OverflowResult computeOverflowForSignedAdd(const AddOperator *Add,
525  const DataLayout &DL,
526  AssumptionCache *AC = nullptr,
527  const Instruction *CxtI = nullptr,
528  const DominatorTree *DT = nullptr);
530  const DataLayout &DL,
531  AssumptionCache *AC,
532  const Instruction *CxtI,
533  const DominatorTree *DT);
534  OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS,
535  const DataLayout &DL,
536  AssumptionCache *AC,
537  const Instruction *CxtI,
538  const DominatorTree *DT);
539 
540  /// Returns true if the arithmetic part of the \p WO 's result is
541  /// used only along the paths control dependent on the computation
542  /// not overflowing, \p WO being an <op>.with.overflow intrinsic.
543  bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO,
544  const DominatorTree &DT);
545 
546 
547  /// Determine the possible constant range of an integer or vector of integer
548  /// value. This is intended as a cheap, non-recursive check.
549  ConstantRange computeConstantRange(const Value *V, bool UseInstrInfo = true,
550  AssumptionCache *AC = nullptr,
551  const Instruction *CtxI = nullptr,
552  const DominatorTree *DT = nullptr,
553  unsigned Depth = 0);
554 
555  /// Return true if this function can prove that the instruction I will
556  /// always transfer execution to one of its successors (including the next
557  /// instruction that follows within a basic block). E.g. this is not
558  /// guaranteed for function calls that could loop infinitely.
559  ///
560  /// In other words, this function returns false for instructions that may
561  /// transfer execution or fail to transfer execution in a way that is not
562  /// captured in the CFG nor in the sequence of instructions within a basic
563  /// block.
564  ///
565  /// Undefined behavior is assumed not to happen, so e.g. division is
566  /// guaranteed to transfer execution to the following instruction even
567  /// though division by zero might cause undefined behavior.
568  bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I);
569 
570  /// Returns true if this block does not contain a potential implicit exit.
571  /// This is equivelent to saying that all instructions within the basic block
572  /// are guaranteed to transfer execution to their successor within the basic
573  /// block. This has the same assumptions w.r.t. undefined behavior as the
574  /// instruction variant of this function.
576 
577  /// Return true if every instruction in the range (Begin, End) is
578  /// guaranteed to transfer execution to its static successor. \p ScanLimit
579  /// bounds the search to avoid scanning huge blocks.
582  unsigned ScanLimit = 32);
583 
584  /// Same as previous, but with range expressed via iterator_range.
586  iterator_range<BasicBlock::const_iterator> Range,
587  unsigned ScanLimit = 32);
588 
589  /// Return true if this function can prove that the instruction I
590  /// is executed for every iteration of the loop L.
591  ///
592  /// Note that this currently only considers the loop header.
593  bool isGuaranteedToExecuteForEveryIteration(const Instruction *I,
594  const Loop *L);
595 
596  /// Return true if I yields poison or raises UB if any of its operands is
597  /// poison.
598  /// Formally, given I = `r = op v1 v2 .. vN`, propagatesPoison returns true
599  /// if, for all i, r is evaluated to poison or op raises UB if vi = poison.
600  /// If vi is a vector or an aggregate and r is a single value, any poison
601  /// element in vi should make r poison or raise UB.
602  /// To filter out operands that raise UB on poison, you can use
603  /// getGuaranteedNonPoisonOp.
604  bool propagatesPoison(const Operator *I);
605 
606  /// Insert operands of I into Ops such that I will trigger undefined behavior
607  /// if I is executed and that operand has a poison value.
608  void getGuaranteedNonPoisonOps(const Instruction *I,
609  SmallPtrSetImpl<const Value *> &Ops);
610  /// Insert operands of I into Ops such that I will trigger undefined behavior
611  /// if I is executed and that operand is not a well-defined value
612  /// (i.e. has undef bits or poison).
613  void getGuaranteedWellDefinedOps(const Instruction *I,
614  SmallPtrSetImpl<const Value *> &Ops);
615 
616  /// Return true if the given instruction must trigger undefined behavior
617  /// when I is executed with any operands which appear in KnownPoison holding
618  /// a poison value at the point of execution.
619  bool mustTriggerUB(const Instruction *I,
620  const SmallSet<const Value *, 16>& KnownPoison);
621 
622  /// Return true if this function can prove that if Inst is executed
623  /// and yields a poison value or undef bits, then that will trigger
624  /// undefined behavior.
625  ///
626  /// Note that this currently only considers the basic block that is
627  /// the parent of Inst.
628  bool programUndefinedIfUndefOrPoison(const Instruction *Inst);
629  bool programUndefinedIfPoison(const Instruction *Inst);
630 
631  /// canCreateUndefOrPoison returns true if Op can create undef or poison from
632  /// non-undef & non-poison operands.
633  /// For vectors, canCreateUndefOrPoison returns true if there is potential
634  /// poison or undef in any element of the result when vectors without
635  /// undef/poison poison are given as operands.
636  /// For example, given `Op = shl <2 x i32> %x, <0, 32>`, this function returns
637  /// true. If Op raises immediate UB but never creates poison or undef
638  /// (e.g. sdiv I, 0), canCreatePoison returns false.
639  ///
640  /// \p ConsiderFlags controls whether poison producing flags on the
641  /// instruction are considered. This can be used to see if the instruction
642  /// could still introduce undef or poison even without poison generating flags
643  /// which might be on the instruction. (i.e. could the result of
644  /// Op->dropPoisonGeneratingFlags() still create poison or undef)
645  ///
646  /// canCreatePoison returns true if Op can create poison from non-poison
647  /// operands.
648  bool canCreateUndefOrPoison(const Operator *Op, bool ConsiderFlags = true);
649  bool canCreatePoison(const Operator *Op, bool ConsiderFlags = true);
650 
651  /// Return true if V is poison given that ValAssumedPoison is already poison.
652  /// For example, if ValAssumedPoison is `icmp X, 10` and V is `icmp X, 5`,
653  /// impliesPoison returns true.
654  bool impliesPoison(const Value *ValAssumedPoison, const Value *V);
655 
656  /// Return true if this function can prove that V does not have undef bits
657  /// and is never poison. If V is an aggregate value or vector, check whether
658  /// all elements (except padding) are not undef or poison.
659  /// Note that this is different from canCreateUndefOrPoison because the
660  /// function assumes Op's operands are not poison/undef.
661  ///
662  /// If CtxI and DT are specified this method performs flow-sensitive analysis
663  /// and returns true if it is guaranteed to be never undef or poison
664  /// immediately before the CtxI.
666  AssumptionCache *AC = nullptr,
667  const Instruction *CtxI = nullptr,
668  const DominatorTree *DT = nullptr,
669  unsigned Depth = 0);
670  bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC = nullptr,
671  const Instruction *CtxI = nullptr,
672  const DominatorTree *DT = nullptr,
673  unsigned Depth = 0);
674 
675  /// Specific patterns of select instructions we can match.
678  SPF_SMIN, /// Signed minimum
679  SPF_UMIN, /// Unsigned minimum
680  SPF_SMAX, /// Signed maximum
681  SPF_UMAX, /// Unsigned maximum
682  SPF_FMINNUM, /// Floating point minnum
683  SPF_FMAXNUM, /// Floating point maxnum
684  SPF_ABS, /// Absolute value
685  SPF_NABS /// Negated absolute value
686  };
687 
688  /// Behavior when a floating point min/max is given one NaN and one
689  /// non-NaN as input.
691  SPNB_NA = 0, /// NaN behavior not applicable.
692  SPNB_RETURNS_NAN, /// Given one NaN input, returns the NaN.
693  SPNB_RETURNS_OTHER, /// Given one NaN input, returns the non-NaN.
694  SPNB_RETURNS_ANY /// Given one NaN input, can return either (or
695  /// it has been determined that no operands can
696  /// be NaN).
697  };
698 
701  SelectPatternNaNBehavior NaNBehavior; /// Only applicable if Flavor is
702  /// SPF_FMINNUM or SPF_FMAXNUM.
703  bool Ordered; /// When implementing this min/max pattern as
704  /// fcmp; select, does the fcmp have to be
705  /// ordered?
706 
707  /// Return true if \p SPF is a min or a max pattern.
708  static bool isMinOrMax(SelectPatternFlavor SPF) {
709  return SPF != SPF_UNKNOWN && SPF != SPF_ABS && SPF != SPF_NABS;
710  }
711  };
712 
713  /// Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind
714  /// and providing the out parameter results if we successfully match.
715  ///
716  /// For ABS/NABS, LHS will be set to the input to the abs idiom. RHS will be
717  /// the negation instruction from the idiom.
718  ///
719  /// If CastOp is not nullptr, also match MIN/MAX idioms where the type does
720  /// not match that of the original select. If this is the case, the cast
721  /// operation (one of Trunc,SExt,Zext) that must be done to transform the
722  /// type of LHS and RHS into the type of V is returned in CastOp.
723  ///
724  /// For example:
725  /// %1 = icmp slt i32 %a, i32 4
726  /// %2 = sext i32 %a to i64
727  /// %3 = select i1 %1, i64 %2, i64 4
728  ///
729  /// -> LHS = %a, RHS = i32 4, *CastOp = Instruction::SExt
730  ///
731  SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS,
732  Instruction::CastOps *CastOp = nullptr,
733  unsigned Depth = 0);
734 
735  inline SelectPatternResult
736  matchSelectPattern(const Value *V, const Value *&LHS, const Value *&RHS) {
737  Value *L = const_cast<Value *>(LHS);
738  Value *R = const_cast<Value *>(RHS);
739  auto Result = matchSelectPattern(const_cast<Value *>(V), L, R);
740  LHS = L;
741  RHS = R;
742  return Result;
743  }
744 
745  /// Determine the pattern that a select with the given compare as its
746  /// predicate and given values as its true/false operands would match.
747  SelectPatternResult matchDecomposedSelectPattern(
748  CmpInst *CmpI, Value *TrueVal, Value *FalseVal, Value *&LHS, Value *&RHS,
749  Instruction::CastOps *CastOp = nullptr, unsigned Depth = 0);
750 
751  /// Return the canonical comparison predicate for the specified
752  /// minimum/maximum flavor.
754  bool Ordered = false);
755 
756  /// Return the inverse minimum/maximum flavor of the specified flavor.
757  /// For example, signed minimum is the inverse of signed maximum.
759 
761 
762  /// Return the canonical inverse comparison predicate for the specified
763  /// minimum/maximum flavor.
765 
766  /// Return the minimum or maximum constant value for the specified integer
767  /// min/max flavor and type.
768  APInt getMinMaxLimit(SelectPatternFlavor SPF, unsigned BitWidth);
769 
770  /// Check if the values in \p VL are select instructions that can be converted
771  /// to a min or max (vector) intrinsic. Returns the intrinsic ID, if such a
772  /// conversion is possible, together with a bool indicating whether all select
773  /// conditions are only used by the selects. Otherwise return
774  /// Intrinsic::not_intrinsic.
775  std::pair<Intrinsic::ID, bool>
776  canConvertToMinOrMaxIntrinsic(ArrayRef<Value *> VL);
777 
778  /// Attempt to match a simple first order recurrence cycle of the form:
779  /// %iv = phi Ty [%Start, %Entry], [%Inc, %backedge]
780  /// %inc = binop %iv, %step
781  /// OR
782  /// %iv = phi Ty [%Start, %Entry], [%Inc, %backedge]
783  /// %inc = binop %step, %iv
784  ///
785  /// A first order recurrence is a formula with the form: X_n = f(X_(n-1))
786  ///
787  /// A couple of notes on subtleties in that definition:
788  /// * The Step does not have to be loop invariant. In math terms, it can
789  /// be a free variable. We allow recurrences with both constant and
790  /// variable coefficients. Callers may wish to filter cases where Step
791  /// does not dominate P.
792  /// * For non-commutative operators, we will match both forms. This
793  /// results in some odd recurrence structures. Callers may wish to filter
794  /// out recurrences where the phi is not the LHS of the returned operator.
795  /// * Because of the structure matched, the caller can assume as a post
796  /// condition of the match the presence of a Loop with P's parent as it's
797  /// header *except* in unreachable code. (Dominance decays in unreachable
798  /// code.)
799  ///
800  /// NOTE: This is intentional simple. If you want the ability to analyze
801  /// non-trivial loop conditons, see ScalarEvolution instead.
802  bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO,
803  Value *&Start, Value *&Step);
804 
805  /// Analogous to the above, but starting from the binary operator
806  bool matchSimpleRecurrence(const BinaryOperator *I, PHINode *&P,
807  Value *&Start, Value *&Step);
808 
809  /// Return true if RHS is known to be implied true by LHS. Return false if
810  /// RHS is known to be implied false by LHS. Otherwise, return None if no
811  /// implication can be made.
812  /// A & B must be i1 (boolean) values or a vector of such values. Note that
813  /// the truth table for implication is the same as <=u on i1 values (but not
814  /// <=s!). The truth table for both is:
815  /// | T | F (B)
816  /// T | T | F
817  /// F | T | T
818  /// (A)
819  Optional<bool> isImpliedCondition(const Value *LHS, const Value *RHS,
820  const DataLayout &DL, bool LHSIsTrue = true,
821  unsigned Depth = 0);
822  Optional<bool> isImpliedCondition(const Value *LHS,
823  CmpInst::Predicate RHSPred,
824  const Value *RHSOp0, const Value *RHSOp1,
825  const DataLayout &DL, bool LHSIsTrue = true,
826  unsigned Depth = 0);
827 
828  /// Return the boolean condition value in the context of the given instruction
829  /// if it is known based on dominating conditions.
830  Optional<bool> isImpliedByDomCondition(const Value *Cond,
831  const Instruction *ContextI,
832  const DataLayout &DL);
833  Optional<bool> isImpliedByDomCondition(CmpInst::Predicate Pred,
834  const Value *LHS, const Value *RHS,
835  const Instruction *ContextI,
836  const DataLayout &DL);
837 
838  /// If Ptr1 is provably equal to Ptr2 plus a constant offset, return that
839  /// offset. For example, Ptr1 might be &A[42], and Ptr2 might be &A[40]. In
840  /// this case offset would be -8.
841  Optional<int64_t> isPointerOffset(const Value *Ptr1, const Value *Ptr2,
842  const DataLayout &DL);
843 } // end namespace llvm
844 
845 #endif // LLVM_ANALYSIS_VALUETRACKING_H
llvm::getGuaranteedNonPoisonOps
void getGuaranteedNonPoisonOps(const Instruction *I, SmallPtrSetImpl< const Value * > &Ops)
Insert operands of I into Ops such that I will trigger undefined behavior if I is executed and that o...
Definition: ValueTracking.cpp:5471
llvm::mustSuppressSpeculation
bool mustSuppressSpeculation(const LoadInst &LI)
Return true if speculation of the given load must be suppressed to avoid ordering or interfering with...
Definition: ValueTracking.cpp:4610
llvm::SPF_SMAX
@ SPF_SMAX
Unsigned minimum.
Definition: ValueTracking.h:680
llvm::isKnownNegative
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.
Definition: ValueTracking.cpp:344
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::haveNoCommonBitsSet
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.
Definition: ValueTracking.cpp:269
llvm::isKnownNonNegative
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.
Definition: ValueTracking.cpp:323
llvm::OverflowResult::NeverOverflows
@ NeverOverflows
Never overflows.
Optional.h
llvm::MaskedValueIsZero
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 'V & Mask' is known to be zero.
Definition: ValueTracking.cpp:367
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::ConstantDataArraySlice::Array
const ConstantDataArray * Array
ConstantDataArray pointer.
Definition: ValueTracking.h:306
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Definition: ValueTracking.cpp:4622
llvm::computeOverflowForUnsignedMul
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
Definition: ValueTracking.cpp:4740
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::isImpliedCondition
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.
Definition: ValueTracking.cpp:6699
llvm::SelectPatternResult::Flavor
SelectPatternFlavor Flavor
Definition: ValueTracking.h:700
llvm::isGuaranteedNotToBeUndefOrPoison
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
Definition: ValueTracking.cpp:5282
llvm::APInt::getSExtValue
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1474
llvm::matchSimpleRecurrence
bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
Definition: ValueTracking.cpp:6384
llvm::SelectPatternResult::NaNBehavior
SelectPatternNaNBehavior NaNBehavior
Definition: ValueTracking.h:701
llvm::ConstantDataSequential::getElementAsInteger
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:3190
llvm::MaxAnalysisRecursionDepth
constexpr unsigned MaxAnalysisRecursionDepth
Definition: ValueTracking.h:48
llvm::computeOverflowForUnsignedAdd
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
Definition: ValueTracking.cpp:4796
llvm::SignBitMustBeZero
bool SignBitMustBeZero(const Value *V, const TargetLibraryInfo *TLI)
Return true if we can prove that the specified FP value's sign bit is 0.
Definition: ValueTracking.cpp:3682
llvm::isKnownPositive
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.
Definition: ValueTracking.cpp:332
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::ConstantDataArraySlice::Offset
uint64_t Offset
Slice starts at this Offset.
Definition: ValueTracking.h:309
llvm::isKnownNonZero
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.
Definition: ValueTracking.cpp:316
llvm::programUndefinedIfPoison
bool programUndefinedIfPoison(const Instruction *Inst)
Definition: ValueTracking.cpp:5601
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::OverflowResult::AlwaysOverflowsLow
@ AlwaysOverflowsLow
Always overflows in the direction of signed/unsigned min value.
llvm::isBytewiseValue
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...
Definition: ValueTracking.cpp:3855
llvm::Value::stripAndAccumulateConstantOffsets
const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr) const
Accumulate the constant offset this value has compared to a base pointer.
llvm::SPF_UMAX
@ SPF_UMAX
Signed maximum.
Definition: ValueTracking.h:681
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::ComputeNumSignBits
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.
Definition: ValueTracking.cpp:391
llvm::tgtok::FalseVal
@ FalseVal
Definition: TGLexer.h:61
Operator.h
llvm::ConstantDataArraySlice::Length
uint64_t Length
Length of the slice.
Definition: ValueTracking.h:312
llvm::SelectPatternNaNBehavior
SelectPatternNaNBehavior
Behavior when a floating point min/max is given one NaN and one non-NaN as input.
Definition: ValueTracking.h:690
llvm::matchSelectPattern
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...
Definition: ValueTracking.cpp:6242
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:676
llvm::getMinMaxLimit
APInt getMinMaxLimit(SelectPatternFlavor SPF, unsigned BitWidth)
Return the minimum or maximum constant value for the specified integer min/max flavor and type.
Definition: ValueTracking.cpp:6334
llvm::BitmaskEnumDetail::Mask
std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
llvm::SPNB_RETURNS_NAN
@ SPNB_RETURNS_NAN
NaN behavior not applicable.
Definition: ValueTracking.h:692
llvm::computeKnownBitsFromRangeMetadata
void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, KnownBits &Known)
Compute known bits from the range metadata.
Definition: ValueTracking.cpp:459
llvm::mustTriggerUB
bool mustTriggerUB(const Instruction *I, const SmallSet< const Value *, 16 > &KnownPoison)
Return true if the given instruction must trigger undefined behavior when I is executed with any oper...
Definition: ValueTracking.cpp:5497
llvm::isPointerOffset
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.
Definition: ValueTracking.cpp:7169
llvm::SPF_NABS
@ SPF_NABS
Absolute value.
Definition: ValueTracking.h:685
llvm::SPF_UNKNOWN
@ SPF_UNKNOWN
Definition: ValueTracking.h:677
llvm::computeOverflowForSignedSub
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
Definition: ValueTracking.cpp:4895
llvm::isValidAssumeForContext
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,...
Definition: ValueTracking.cpp:529
Constants.h
llvm::computeOverflowForSignedAdd
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Definition: ValueTracking.cpp:5304
llvm::OverflowResult::MayOverflow
@ MayOverflow
May or may not overflow.
Intrinsics.h
InstrTypes.h
llvm::SelectPatternResult::isMinOrMax
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?
Definition: ValueTracking.h:708
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::Instruction::CastOps
CastOps
Definition: Instruction.h:799
llvm::Instruction
Definition: Instruction.h:45
llvm::ComputeMultiple
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.
Definition: ValueTracking.cpp:3245
llvm::getInverseMinMaxFlavor
SelectPatternFlavor getInverseMinMaxFlavor(SelectPatternFlavor SPF)
Return the inverse minimum/maximum flavor of the specified flavor.
Definition: ValueTracking.cpp:6312
llvm::getArgumentAliasingToReturnedPointer
const Value * getArgumentAliasingToReturnedPointer(const CallBase *Call, bool MustPreserveNullness)
This function returns call pointer argument that is considered the same by aliasing rules.
Definition: ValueTracking.cpp:4334
llvm::getUnderlyingObject
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
Definition: ValueTracking.cpp:4389
llvm::isGEPBasedOnPointerToString
bool isGEPBasedOnPointerToString(const GEPOperator *GEP, unsigned CharSize=8)
Returns true if the GEP is based on a pointer to a string (array of.
Definition: ValueTracking.cpp:4123
llvm::impliesPoison
bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
Definition: ValueTracking.cpp:5146
llvm::SPF_SMIN
@ SPF_SMIN
Definition: ValueTracking.h:678
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::mayBeMemoryDependent
bool mayBeMemoryDependent(const Instruction &I)
Returns true if the result or effects of the given instructions I depend on or influence global memor...
Definition: ValueTracking.cpp:4707
llvm::onlyUsedByLifetimeMarkersOrDroppableInsts
bool onlyUsedByLifetimeMarkersOrDroppableInsts(const Value *V)
Return true if the only users of this pointer are lifetime markers or droppable instructions.
Definition: ValueTracking.cpp:4605
llvm::OverflowResult
OverflowResult
Definition: ValueTracking.h:487
llvm::SelectPatternResult
Definition: ValueTracking.h:699
llvm::isOnlyUsedInZeroEqualityComparison
bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI)
Definition: ValueTracking.cpp:293
llvm::canCreatePoison
bool canCreatePoison(const Operator *Op, bool ConsiderFlags=true)
Definition: ValueTracking.cpp:5090
llvm::getUnderlyingObjects
void getUnderlyingObjects(const Value *V, SmallVectorImpl< const Value * > &Objects, LoopInfo *LI=nullptr, unsigned MaxLookup=6)
This method is similar to getUnderlyingObject except that it can look through phi and select instruct...
Definition: ValueTracking.cpp:4434
llvm::matchDecomposedSelectPattern
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...
Definition: ValueTracking.cpp:6261
llvm::isGuaranteedToExecuteForEveryIteration
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 ...
Definition: ValueTracking.cpp:5375
uint64_t
llvm::getConstantStringInfo
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.
Definition: ValueTracking.cpp:4221
llvm::computeOverflowForUnsignedSub
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
Definition: ValueTracking.cpp:4872
llvm::ConstantDataArray
An array constant whose element type is a simple 1/2/4/8-byte integer or float/double,...
Definition: Constants.h:678
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::SPNB_NA
@ SPNB_NA
Definition: ValueTracking.h:691
ArrayRef.h
llvm::isKnownNonEqual
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.
Definition: ValueTracking.cpp:355
llvm::computeKnownBits
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...
Definition: ValueTracking.cpp:224
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SPNB_RETURNS_ANY
@ SPNB_RETURNS_ANY
Given one NaN input, returns the non-NaN.
Definition: ValueTracking.h:694
llvm::SPF_ABS
@ SPF_ABS
Floating point maxnum.
Definition: ValueTracking.h:684
llvm::isKnownNegation
bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW=false)
Return true if the two given values are negation.
Definition: ValueTracking.cpp:5931
llvm::getUnderlyingObjectsForCodeGen
bool getUnderlyingObjectsForCodeGen(const Value *V, SmallVectorImpl< Value * > &Objects)
This is a wrapper around getUnderlyingObjects and adds support for basic ptrtoint+arithmetic+inttoptr...
Definition: ValueTracking.cpp:4505
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::MDNode
Metadata node.
Definition: Metadata.h:906
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::ArrayRef< unsigned >
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
DataLayout.h
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::getConstantDataArrayInfo
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.
Definition: ValueTracking.cpp:4144
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::ConstantDataArraySlice::operator[]
uint64_t operator[](unsigned I) const
Convenience accessor for elements in the slice.
Definition: ValueTracking.h:322
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::canCreateUndefOrPoison
bool canCreateUndefOrPoison(const Operator *Op, bool ConsiderFlags=true)
canCreateUndefOrPoison returns true if Op can create undef or poison from non-undef & non-poison oper...
Definition: ValueTracking.cpp:5086
llvm::SPF_FMINNUM
@ SPF_FMINNUM
Unsigned maximum.
Definition: ValueTracking.h:682
llvm::getInverseMinMaxPred
CmpInst::Predicate getInverseMinMaxPred(SelectPatternFlavor SPF)
Return the canonical inverse comparison predicate for the specified minimum/maximum flavor.
Definition: ValueTracking.cpp:6330
llvm::isKnownNeverInfinity
bool isKnownNeverInfinity(const Value *V, const TargetLibraryInfo *TLI, unsigned Depth=0)
Return true if the floating-point scalar value is not an infinity or if the floating-point vector val...
Definition: ValueTracking.cpp:3686
llvm::SPF_FMAXNUM
@ SPF_FMAXNUM
Floating point minnum.
Definition: ValueTracking.h:683
llvm::isKnownNeverNaN
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...
Definition: ValueTracking.cpp:3750
llvm::isAssumeLikeIntrinsic
bool isAssumeLikeIntrinsic(const Instruction *I)
Return true if it is an intrinsic that cannot be speculated but also cannot trap.
Definition: ValueTracking.cpp:522
llvm::computeConstantRange
ConstantRange computeConstantRange(const Value *V, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
Definition: ValueTracking.cpp:7077
llvm::onlyUsedByLifetimeMarkers
bool onlyUsedByLifetimeMarkers(const Value *V)
Return true if the only users of this pointer are lifetime markers.
Definition: ValueTracking.cpp:4601
llvm::GetStringLength
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 'len+1'.
Definition: ValueTracking.cpp:4322
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::FindInsertedValue
Value * FindInsertedValue(Value *V, ArrayRef< unsigned > idx_range, Instruction *InsertBefore=nullptr)
Given an aggregate and an sequence of indices, see if the scalar value indexed is already around as a...
Definition: ValueTracking.cpp:4039
llvm::KnownBits
Definition: KnownBits.h:23
llvm::SelectPatternResult::Ordered
bool Ordered
Only applicable if Flavor is SPF_FMINNUM or SPF_FMAXNUM.
Definition: ValueTracking.h:703
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:324
llvm::isOverflowIntrinsicNoWrap
bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO, const DominatorTree &DT)
Returns true if the arithmetic part of the WO 's result is used only along the paths control dependen...
Definition: ValueTracking.cpp:4914
llvm::isGuaranteedToTransferExecutionToSuccessor
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
Definition: ValueTracking.cpp:5313
llvm::getIntrinsicForCallSite
Intrinsic::ID getIntrinsicForCallSite(const CallBase &CB, const TargetLibraryInfo *TLI)
Map a call instruction to an intrinsic ID.
Definition: ValueTracking.cpp:3360
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:221
llvm::CannotBeOrderedLessThanZero
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....
Definition: ValueTracking.cpp:3677
llvm::OverflowResult::AlwaysOverflowsHigh
@ AlwaysOverflowsHigh
Always overflows in the direction of signed/unsigned max value.
llvm::GetPointerBaseWithConstantOffset
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.
Definition: ValueTracking.h:279
llvm::getInverseMinMaxIntrinsic
Intrinsic::ID getInverseMinMaxIntrinsic(Intrinsic::ID MinMaxID)
Definition: ValueTracking.cpp:6320
llvm::computeOverflowForSignedMul
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
Definition: ValueTracking.cpp:4754
llvm::CannotBeNegativeZero
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.
Definition: ValueTracking.cpp:3473
llvm::isImpliedByDomCondition
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...
Definition: ValueTracking.cpp:6745
llvm::SPF_UMIN
@ SPF_UMIN
Signed minimum.
Definition: ValueTracking.h:679
llvm::getMinMaxPred
CmpInst::Predicate getMinMaxPred(SelectPatternFlavor SPF, bool Ordered=false)
Return the canonical comparison predicate for the specified minimum/maximum flavor.
Definition: ValueTracking.cpp:6300
llvm::SPNB_RETURNS_OTHER
@ SPNB_RETURNS_OTHER
Given one NaN input, returns the NaN.
Definition: ValueTracking.h:693
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
llvm::propagatesPoison
bool propagatesPoison(const Operator *I)
Return true if I yields poison or raises UB if any of its operands is poison.
Definition: ValueTracking.cpp:5390
llvm::isGuaranteedNotToBePoison
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Definition: ValueTracking.cpp:5289
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::ConstantDataArraySlice
Represents offset+length into a ConstantDataArray.
Definition: ValueTracking.h:303
llvm::isKnownToBeAPowerOfTwo
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.
Definition: ValueTracking.cpp:303
llvm::ConstantDataArraySlice::move
void move(uint64_t Delta)
Moves the Offset and adjusts Length accordingly.
Definition: ValueTracking.h:315
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:62
llvm::programUndefinedIfUndefOrPoison
bool programUndefinedIfUndefOrPoison(const Instruction *Inst)
Return true if this function can prove that if Inst is executed and yields a poison value or undef bi...
Definition: ValueTracking.cpp:5597
llvm::canConvertToMinOrMaxIntrinsic
std::pair< Intrinsic::ID, bool > canConvertToMinOrMaxIntrinsic(ArrayRef< Value * > VL)
Check if the values in VL are select instructions that can be converted to a min or max (vector) intr...
Definition: ValueTracking.cpp:6345
llvm::tgtok::TrueVal
@ TrueVal
Definition: TGLexer.h:61
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::getGuaranteedWellDefinedOps
void getGuaranteedWellDefinedOps(const Instruction *I, SmallPtrSetImpl< const Value * > &Ops)
Insert operands of I into Ops such that I will trigger undefined behavior if I is executed and that o...
Definition: ValueTracking.cpp:5429
llvm::isIntrinsicReturningPointerAliasingArgumentWithoutCapturing
bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(const CallBase *Call, bool MustPreserveNullness)
{launder,strip}.invariant.group returns pointer that aliases its argument, and it only captures point...
Definition: ValueTracking.cpp:4347
llvm::findAllocaForValue
AllocaInst * findAllocaForValue(Value *V, bool OffsetZero=false)
Returns unique alloca where the value comes from, or nullptr.
Definition: ValueTracking.cpp:4538
llvm::BasicBlock::const_iterator
InstListType::const_iterator const_iterator
Definition: BasicBlock.h:91
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
SmallSet.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37