LLVM  15.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 <cassert>
25 #include <cstdint>
26 
27 namespace llvm {
28 
29 class Operator;
30 class AddOperator;
31 class AllocaInst;
32 class APInt;
33 class AssumptionCache;
34 class DominatorTree;
35 class GEPOperator;
36 class LoadInst;
37 class WithOverflowInst;
38 struct KnownBits;
39 class Loop;
40 class LoopInfo;
41 class MDNode;
42 class OptimizationRemarkEmitter;
43 class StringRef;
44 class TargetLibraryInfo;
45 class Value;
46 
47 constexpr unsigned MaxAnalysisRecursionDepth = 6;
48 
49  /// Determine which bits of V are known to be either zero or one and return
50  /// them in the KnownZero/KnownOne bit sets.
51  ///
52  /// This function is defined on values with integer type, values with pointer
53  /// type, and vectors of integers. In the case
54  /// where V is a vector, the known zero and known one values are the
55  /// same width as the vector element, and the bit is set only if it is true
56  /// for all of the elements in the vector.
57  void computeKnownBits(const Value *V, KnownBits &Known,
58  const DataLayout &DL, unsigned Depth = 0,
59  AssumptionCache *AC = nullptr,
60  const Instruction *CxtI = nullptr,
61  const DominatorTree *DT = nullptr,
62  OptimizationRemarkEmitter *ORE = nullptr,
63  bool UseInstrInfo = true);
64 
65  /// Determine which bits of V are known to be either zero or one and return
66  /// them in the KnownZero/KnownOne bit sets.
67  ///
68  /// This function is defined on values with integer type, values with pointer
69  /// type, and vectors of integers. In the case
70  /// where V is a vector, the known zero and known one values are the
71  /// same width as the vector element, and the bit is set only if it is true
72  /// for all of the demanded elements in the vector.
73  void computeKnownBits(const Value *V, const APInt &DemandedElts,
74  KnownBits &Known, const DataLayout &DL,
75  unsigned Depth = 0, AssumptionCache *AC = nullptr,
76  const Instruction *CxtI = nullptr,
77  const DominatorTree *DT = nullptr,
78  OptimizationRemarkEmitter *ORE = nullptr,
79  bool UseInstrInfo = true);
80 
81  /// Returns the known bits rather than passing by reference.
82  KnownBits computeKnownBits(const Value *V, const DataLayout &DL,
83  unsigned Depth = 0, AssumptionCache *AC = nullptr,
84  const Instruction *CxtI = nullptr,
85  const DominatorTree *DT = nullptr,
86  OptimizationRemarkEmitter *ORE = nullptr,
87  bool UseInstrInfo = true);
88 
89  /// Returns the known bits rather than passing by reference.
90  KnownBits computeKnownBits(const Value *V, const APInt &DemandedElts,
91  const DataLayout &DL, unsigned Depth = 0,
92  AssumptionCache *AC = nullptr,
93  const Instruction *CxtI = nullptr,
94  const DominatorTree *DT = nullptr,
95  OptimizationRemarkEmitter *ORE = nullptr,
96  bool UseInstrInfo = true);
97 
98  /// Compute known bits from the range metadata.
99  /// \p KnownZero the set of bits that are known to be zero
100  /// \p KnownOne the set of bits that are known to be one
101  void computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
102  KnownBits &Known);
103 
104  /// Return true if LHS and RHS have no common bits set.
105  bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS,
106  const DataLayout &DL,
107  AssumptionCache *AC = nullptr,
108  const Instruction *CxtI = nullptr,
109  const DominatorTree *DT = nullptr,
110  bool UseInstrInfo = true);
111 
112  /// Return true if the given value is known to have exactly one bit set when
113  /// defined. For vectors return true if every element is known to be a power
114  /// of two when defined. Supports values with integer or pointer type and
115  /// vectors of integers. If 'OrZero' is set, then return true if the given
116  /// value is either a power of two or zero.
117  bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL,
118  bool OrZero = false, unsigned Depth = 0,
119  AssumptionCache *AC = nullptr,
120  const Instruction *CxtI = nullptr,
121  const DominatorTree *DT = nullptr,
122  bool UseInstrInfo = true);
123 
125 
126  /// Return true if the given value is known to be non-zero when defined. For
127  /// vectors, return true if every element is known to be non-zero when
128  /// defined. For pointers, if the context instruction and dominator tree are
129  /// specified, perform context-sensitive analysis and return true if the
130  /// pointer couldn't possibly be null at the specified instruction.
131  /// Supports values with integer or pointer type and vectors of integers.
132  bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth = 0,
133  AssumptionCache *AC = nullptr,
134  const Instruction *CxtI = nullptr,
135  const DominatorTree *DT = nullptr,
136  bool UseInstrInfo = true);
137 
138  /// Return true if the two given values are negation.
139  /// Currently can recoginze Value pair:
140  /// 1: <X, Y> if X = sub (0, Y) or Y = sub (0, X)
141  /// 2: <X, Y> if X = sub (A, B) and Y = sub (B, A)
142  bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW = false);
143 
144  /// Returns true if the give value is known to be non-negative.
145  bool isKnownNonNegative(const Value *V, const DataLayout &DL,
146  unsigned Depth = 0,
147  AssumptionCache *AC = nullptr,
148  const Instruction *CxtI = nullptr,
149  const DominatorTree *DT = nullptr,
150  bool UseInstrInfo = true);
151 
152  /// Returns true if the given value is known be positive (i.e. non-negative
153  /// and non-zero).
154  bool isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth = 0,
155  AssumptionCache *AC = nullptr,
156  const Instruction *CxtI = nullptr,
157  const DominatorTree *DT = nullptr,
158  bool UseInstrInfo = true);
159 
160  /// Returns true if the given value is known be negative (i.e. non-positive
161  /// and non-zero).
162  bool isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth = 0,
163  AssumptionCache *AC = nullptr,
164  const Instruction *CxtI = nullptr,
165  const DominatorTree *DT = nullptr,
166  bool UseInstrInfo = true);
167 
168  /// Return true if the given values are known to be non-equal when defined.
169  /// Supports scalar integer types only.
170  bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL,
171  AssumptionCache *AC = nullptr,
172  const Instruction *CxtI = nullptr,
173  const DominatorTree *DT = nullptr,
174  bool UseInstrInfo = true);
175 
176  /// Return true if 'V & Mask' is known to be zero. We use this predicate to
177  /// simplify operations downstream. Mask is known to be zero for bits that V
178  /// cannot have.
179  ///
180  /// This function is defined on values with integer type, values with pointer
181  /// type, and vectors of integers. In the case
182  /// where V is a vector, the mask, known zero, and known one values are the
183  /// same width as the vector element, and the bit is set only if it is true
184  /// for all of the elements in the vector.
185  bool MaskedValueIsZero(const Value *V, const APInt &Mask,
186  const DataLayout &DL,
187  unsigned Depth = 0, AssumptionCache *AC = nullptr,
188  const Instruction *CxtI = nullptr,
189  const DominatorTree *DT = nullptr,
190  bool UseInstrInfo = true);
191 
192  /// Return the number of times the sign bit of the register is replicated into
193  /// the other bits. We know that at least 1 bit is always equal to the sign
194  /// bit (itself), but other cases can give us information. For example,
195  /// immediately after an "ashr X, 2", we know that the top 3 bits are all
196  /// equal to each other, so we return 3. For vectors, return the number of
197  /// sign bits for the vector element with the mininum number of known sign
198  /// bits.
199  unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL,
200  unsigned Depth = 0, AssumptionCache *AC = nullptr,
201  const Instruction *CxtI = nullptr,
202  const DominatorTree *DT = nullptr,
203  bool UseInstrInfo = true);
204 
205  /// Get the upper bound on bit size for this Value \p Op as a signed integer.
206  /// i.e. x == sext(trunc(x to MaxSignificantBits) to bitwidth(x)).
207  /// Similar to the APInt::getSignificantBits function.
208  unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL,
209  unsigned Depth = 0,
210  AssumptionCache *AC = nullptr,
211  const Instruction *CxtI = nullptr,
212  const DominatorTree *DT = nullptr);
213 
214  /// Map a call instruction to an intrinsic ID. Libcalls which have equivalent
215  /// intrinsics are treated as-if they were intrinsics.
217  const TargetLibraryInfo *TLI);
218 
219  /// Return true if we can prove that the specified FP value is never equal to
220  /// -0.0.
221  bool CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI,
222  unsigned Depth = 0);
223 
224  /// Return true if we can prove that the specified FP value is either NaN or
225  /// never less than -0.0.
226  ///
227  /// NaN --> true
228  /// +0 --> true
229  /// -0 --> true
230  /// x > +0 --> true
231  /// x < -0 --> false
232  bool CannotBeOrderedLessThanZero(const Value *V, const TargetLibraryInfo *TLI);
233 
234  /// Return true if the floating-point scalar value is not an infinity or if
235  /// the floating-point vector value has no infinities. Return false if a value
236  /// could ever be infinity.
237  bool isKnownNeverInfinity(const Value *V, const TargetLibraryInfo *TLI,
238  unsigned Depth = 0);
239 
240  /// Return true if the floating-point scalar value is not a NaN or if the
241  /// floating-point vector value has no NaN elements. Return false if a value
242  /// could ever be NaN.
243  bool isKnownNeverNaN(const Value *V, const TargetLibraryInfo *TLI,
244  unsigned Depth = 0);
245 
246  /// Return true if we can prove that the specified FP value's sign bit is 0.
247  ///
248  /// NaN --> true/false (depending on the NaN's sign bit)
249  /// +0 --> true
250  /// -0 --> false
251  /// x > +0 --> true
252  /// x < -0 --> false
253  bool SignBitMustBeZero(const Value *V, const TargetLibraryInfo *TLI);
254 
255  /// If the specified value can be set by repeating the same byte in memory,
256  /// return the i8 value that it is represented with. This is true for all i8
257  /// values obviously, but is also true for i32 0, i32 -1, i16 0xF0F0, double
258  /// 0.0 etc. If the value can't be handled with a repeated byte store (e.g.
259  /// i16 0x1234), return null. If the value is entirely undef and padding,
260  /// return undef.
261  Value *isBytewiseValue(Value *V, const DataLayout &DL);
262 
263  /// Given an aggregate and an sequence of indices, see if the scalar value
264  /// indexed is already around as a register, for example if it were inserted
265  /// directly into the aggregate.
266  ///
267  /// If InsertBefore is not null, this function will duplicate (modified)
268  /// insertvalues when a part of a nested struct is extracted.
270  ArrayRef<unsigned> idx_range,
271  Instruction *InsertBefore = nullptr);
272 
273  /// Analyze the specified pointer to see if it can be expressed as a base
274  /// pointer plus a constant offset. Return the base and offset to the caller.
275  ///
276  /// This is a wrapper around Value::stripAndAccumulateConstantOffsets that
277  /// creates and later unpacks the required APInt.
279  const DataLayout &DL,
280  bool AllowNonInbounds = true) {
281  APInt OffsetAPInt(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
282  Value *Base =
283  Ptr->stripAndAccumulateConstantOffsets(DL, OffsetAPInt, AllowNonInbounds);
284 
285  Offset = OffsetAPInt.getSExtValue();
286  return Base;
287  }
288  inline const Value *
290  const DataLayout &DL,
291  bool AllowNonInbounds = true) {
292  return GetPointerBaseWithConstantOffset(const_cast<Value *>(Ptr), Offset, DL,
293  AllowNonInbounds);
294  }
295 
296  /// Returns true if the GEP is based on a pointer to a string (array of
297  // \p CharSize integers) and is indexing into this string.
298  bool isGEPBasedOnPointerToString(const GEPOperator *GEP,
299  unsigned CharSize = 8);
300 
301  /// Represents offset+length into a ConstantDataArray.
303  /// ConstantDataArray pointer. nullptr indicates a zeroinitializer (a valid
304  /// initializer, it just doesn't fit the ConstantDataArray interface).
306 
307  /// Slice starts at this Offset.
309 
310  /// Length of the slice.
312 
313  /// Moves the Offset and adjusts Length accordingly.
314  void move(uint64_t Delta) {
315  assert(Delta < Length);
316  Offset += Delta;
317  Length -= Delta;
318  }
319 
320  /// Convenience accessor for elements in the slice.
321  uint64_t operator[](unsigned I) const {
322  return Array==nullptr ? 0 : Array->getElementAsInteger(I + Offset);
323  }
324  };
325 
326  /// Returns true if the value \p V is a pointer into a ConstantDataArray.
327  /// If successful \p Slice will point to a ConstantDataArray info object
328  /// with an appropriate offset.
329  bool getConstantDataArrayInfo(const Value *V, ConstantDataArraySlice &Slice,
330  unsigned ElementSize, uint64_t Offset = 0);
331 
332  /// This function computes the length of a null-terminated C string pointed to
333  /// by V. If successful, it returns true and returns the string in Str. If
334  /// unsuccessful, it returns false. This does not include the trailing null
335  /// character by default. If TrimAtNul is set to false, then this returns any
336  /// trailing null characters as well as any other characters that come after
337  /// it.
338  bool getConstantStringInfo(const Value *V, StringRef &Str,
339  uint64_t Offset = 0, bool TrimAtNul = true);
340 
341  /// If we can compute the length of the string pointed to by the specified
342  /// pointer, return 'len+1'. If we can't, return 0.
343  uint64_t GetStringLength(const Value *V, unsigned CharSize = 8);
344 
345  /// This function returns call pointer argument that is considered the same by
346  /// aliasing rules. You CAN'T use it to replace one value with another. If
347  /// \p MustPreserveNullness is true, the call must preserve the nullness of
348  /// the pointer.
349  const Value *getArgumentAliasingToReturnedPointer(const CallBase *Call,
350  bool MustPreserveNullness);
351  inline Value *
353  bool MustPreserveNullness) {
354  return const_cast<Value *>(getArgumentAliasingToReturnedPointer(
355  const_cast<const CallBase *>(Call), MustPreserveNullness));
356  }
357 
358  /// {launder,strip}.invariant.group returns pointer that aliases its argument,
359  /// and it only captures pointer by returning it.
360  /// These intrinsics are not marked as nocapture, because returning is
361  /// considered as capture. The arguments are not marked as returned neither,
362  /// because it would make it useless. If \p MustPreserveNullness is true,
363  /// the intrinsic must preserve the nullness of the pointer.
365  const CallBase *Call, bool MustPreserveNullness);
366 
367  /// This method strips off any GEP address adjustments and pointer casts from
368  /// the specified value, returning the original object being addressed. Note
369  /// that the returned value has pointer type if the specified value does. If
370  /// the MaxLookup value is non-zero, it limits the number of instructions to
371  /// be stripped off.
372  const Value *getUnderlyingObject(const Value *V, unsigned MaxLookup = 6);
373  inline Value *getUnderlyingObject(Value *V, unsigned MaxLookup = 6) {
374  // Force const to avoid infinite recursion.
375  const Value *VConst = V;
376  return const_cast<Value *>(getUnderlyingObject(VConst, MaxLookup));
377  }
378 
379  /// This method is similar to getUnderlyingObject except that it can
380  /// look through phi and select instructions and return multiple objects.
381  ///
382  /// If LoopInfo is passed, loop phis are further analyzed. If a pointer
383  /// accesses different objects in each iteration, we don't look through the
384  /// phi node. E.g. consider this loop nest:
385  ///
386  /// int **A;
387  /// for (i)
388  /// for (j) {
389  /// A[i][j] = A[i-1][j] * B[j]
390  /// }
391  ///
392  /// This is transformed by Load-PRE to stash away A[i] for the next iteration
393  /// of the outer loop:
394  ///
395  /// Curr = A[0]; // Prev_0
396  /// for (i: 1..N) {
397  /// Prev = Curr; // Prev = PHI (Prev_0, Curr)
398  /// Curr = A[i];
399  /// for (j: 0..N) {
400  /// Curr[j] = Prev[j] * B[j]
401  /// }
402  /// }
403  ///
404  /// Since A[i] and A[i-1] are independent pointers, getUnderlyingObjects
405  /// should not assume that Curr and Prev share the same underlying object thus
406  /// it shouldn't look through the phi above.
407  void getUnderlyingObjects(const Value *V,
408  SmallVectorImpl<const Value *> &Objects,
409  LoopInfo *LI = nullptr, unsigned MaxLookup = 6);
410 
411  /// This is a wrapper around getUnderlyingObjects and adds support for basic
412  /// ptrtoint+arithmetic+inttoptr sequences.
414  SmallVectorImpl<Value *> &Objects);
415 
416  /// Returns unique alloca where the value comes from, or nullptr.
417  /// If OffsetZero is true check that V points to the begining of the alloca.
418  AllocaInst *findAllocaForValue(Value *V, bool OffsetZero = false);
419  inline const AllocaInst *findAllocaForValue(const Value *V,
420  bool OffsetZero = false) {
421  return findAllocaForValue(const_cast<Value *>(V), OffsetZero);
422  }
423 
424  /// Return true if the only users of this pointer are lifetime markers.
425  bool onlyUsedByLifetimeMarkers(const Value *V);
426 
427  /// Return true if the only users of this pointer are lifetime markers or
428  /// droppable instructions.
430 
431  /// Return true if speculation of the given load must be suppressed to avoid
432  /// ordering or interfering with an active sanitizer. If not suppressed,
433  /// dereferenceability and alignment must be proven separately. Note: This
434  /// is only needed for raw reasoning; if you use the interface below
435  /// (isSafeToSpeculativelyExecute), this is handled internally.
436  bool mustSuppressSpeculation(const LoadInst &LI);
437 
438  /// Return true if the instruction does not have any effects besides
439  /// calculating the result and does not have undefined behavior.
440  ///
441  /// This method never returns true for an instruction that returns true for
442  /// mayHaveSideEffects; however, this method also does some other checks in
443  /// addition. It checks for undefined behavior, like dividing by zero or
444  /// loading from an invalid pointer (but not for undefined results, like a
445  /// shift with a shift amount larger than the width of the result). It checks
446  /// for malloc and alloca because speculatively executing them might cause a
447  /// memory leak. It also returns false for instructions related to control
448  /// flow, specifically terminators and PHI nodes.
449  ///
450  /// If the CtxI is specified this method performs context-sensitive analysis
451  /// and returns true if it is safe to execute the instruction immediately
452  /// before the CtxI.
453  ///
454  /// If the CtxI is NOT specified this method only looks at the instruction
455  /// itself and its operands, so if this method returns true, it is safe to
456  /// move the instruction as long as the correct dominance relationships for
457  /// the operands and users hold.
458  ///
459  /// This method can return true for instructions that read memory;
460  /// for such instructions, moving them may change the resulting value.
461  bool isSafeToSpeculativelyExecute(const Value *V,
462  const Instruction *CtxI = nullptr,
463  const DominatorTree *DT = nullptr,
464  const TargetLibraryInfo *TLI = nullptr);
465 
466  /// Returns true if the result or effects of the given instructions \p I
467  /// depend values not reachable through the def use graph.
468  /// * Memory dependence arises for example if the instruction reads from
469  /// memory or may produce effects or undefined behaviour. Memory dependent
470  /// instructions generally cannot be reorderd with respect to other memory
471  /// dependent instructions.
472  /// * Control dependence arises for example if the instruction may fault
473  /// if lifted above a throwing call or infinite loop.
474  bool mayHaveNonDefUseDependency(const Instruction &I);
475 
476  /// Return true if it is an intrinsic that cannot be speculated but also
477  /// cannot trap.
478  bool isAssumeLikeIntrinsic(const Instruction *I);
479 
480  /// Return true if it is valid to use the assumptions provided by an
481  /// assume intrinsic, I, at the point in the control-flow identified by the
482  /// context instruction, CxtI.
483  bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI,
484  const DominatorTree *DT = nullptr);
485 
486  enum class OverflowResult {
487  /// Always overflows in the direction of signed/unsigned min value.
489  /// Always overflows in the direction of signed/unsigned max value.
491  /// May or may not overflow.
492  MayOverflow,
493  /// Never overflows.
495  };
496 
498  const Value *RHS,
499  const DataLayout &DL,
500  AssumptionCache *AC,
501  const Instruction *CxtI,
502  const DominatorTree *DT,
503  bool UseInstrInfo = true);
505  const DataLayout &DL,
506  AssumptionCache *AC,
507  const Instruction *CxtI,
508  const DominatorTree *DT,
509  bool UseInstrInfo = true);
511  const Value *RHS,
512  const DataLayout &DL,
513  AssumptionCache *AC,
514  const Instruction *CxtI,
515  const DominatorTree *DT,
516  bool UseInstrInfo = true);
518  const DataLayout &DL,
519  AssumptionCache *AC = nullptr,
520  const Instruction *CxtI = nullptr,
521  const DominatorTree *DT = nullptr);
522  /// This version also leverages the sign bit of Add if known.
523  OverflowResult computeOverflowForSignedAdd(const AddOperator *Add,
524  const DataLayout &DL,
525  AssumptionCache *AC = nullptr,
526  const Instruction *CxtI = nullptr,
527  const DominatorTree *DT = nullptr);
529  const DataLayout &DL,
530  AssumptionCache *AC,
531  const Instruction *CxtI,
532  const DominatorTree *DT);
534  const DataLayout &DL,
535  AssumptionCache *AC,
536  const Instruction *CxtI,
537  const DominatorTree *DT);
538 
539  /// Returns true if the arithmetic part of the \p WO 's result is
540  /// used only along the paths control dependent on the computation
541  /// not overflowing, \p WO being an <op>.with.overflow intrinsic.
542  bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO,
543  const DominatorTree &DT);
544 
545 
546  /// Determine the possible constant range of an integer or vector of integer
547  /// value. This is intended as a cheap, non-recursive check.
548  ConstantRange computeConstantRange(const Value *V, bool ForSigned,
549  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:5456
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:4583
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:368
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:267
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:347
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:391
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::mayHaveNonDefUseDependency
bool mayHaveNonDefUseDependency(const Instruction &I)
Returns true if the result or effects of the given instructions I depend values not reachable through...
Definition: ValueTracking.cpp:4680
llvm::ConstantDataArraySlice::Array
const ConstantDataArray * Array
ConstantDataArray pointer.
Definition: ValueTracking.h:305
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
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:4595
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:4725
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:6670
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:5267
llvm::APInt::getSExtValue
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1490
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:6355
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:3215
llvm::MaxAnalysisRecursionDepth
constexpr unsigned MaxAnalysisRecursionDepth
Definition: ValueTracking.h:47
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:4781
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:3655
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:356
llvm::ComputeMaxSignificantBits
unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Get the upper bound on bit size for this Value Op as a signed integer.
Definition: ValueTracking.cpp:423
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::ConstantDataArraySlice::Offset
uint64_t Offset
Slice starts at this Offset.
Definition: ValueTracking.h:308
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:340
llvm::programUndefinedIfPoison
bool programUndefinedIfPoison(const Instruction *Inst)
Definition: ValueTracking.cpp:5586
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:3828
llvm::SPF_UMAX
@ SPF_UMAX
Signed maximum.
Definition: ValueTracking.h:681
llvm::Value::stripAndAccumulateConstantOffsets
const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, bool AllowInvariantGroup=false, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr) const
Accumulate the constant offset this value has compared to a base pointer.
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:79
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:415
llvm::tgtok::FalseVal
@ FalseVal
Definition: TGLexer.h:61
llvm::ConstantDataArraySlice::Length
uint64_t Length
Length of the slice.
Definition: ValueTracking.h:311
llvm::SelectPatternNaNBehavior
SelectPatternNaNBehavior
Behavior when a floating point min/max is given one NaN and one non-NaN as input.
Definition: ValueTracking.h:690
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
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:6213
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:6305
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:496
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:5482
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:7198
llvm::BitmaskEnumDetail::Mask
constexpr 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::SPF_NABS
@ SPF_NABS
Absolute value.
Definition: ValueTracking.h:685
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
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:4889
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:566
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:5289
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:800
llvm::Instruction
Definition: Instruction.h:42
llvm::getInverseMinMaxFlavor
SelectPatternFlavor getInverseMinMaxFlavor(SelectPatternFlavor SPF)
Return the inverse minimum/maximum flavor of the specified flavor.
Definition: ValueTracking.cpp:6283
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:4307
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:4362
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:4096
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:5129
llvm::SPF_SMIN
@ SPF_SMIN
Definition: ValueTracking.h:678
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
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:4578
llvm::OverflowResult
OverflowResult
Definition: ValueTracking.h:486
llvm::SelectPatternResult
Definition: ValueTracking.h:699
llvm::isOnlyUsedInZeroEqualityComparison
bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI)
Definition: ValueTracking.cpp:317
llvm::canCreatePoison
bool canCreatePoison(const Operator *Op, bool ConsiderFlags=true)
Definition: ValueTracking.cpp:5073
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:4407
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:6232
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:5360
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:4194
llvm::computeOverflowForUnsignedSub
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
Definition: ValueTracking.cpp:4857
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:58
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:379
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:222
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:5902
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:4478
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::MDNode
Metadata node.
Definition: Metadata.h:937
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:137
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:4117
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::ConstantDataArraySlice::operator[]
uint64_t operator[](unsigned I) const
Convenience accessor for elements in the slice.
Definition: ValueTracking.h:321
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::computeConstantRange
ConstantRange computeConstantRange(const Value *V, bool ForSigned, 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:7102
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:5069
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:6301
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:3659
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:3723
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:559
llvm::onlyUsedByLifetimeMarkers
bool onlyUsedByLifetimeMarkers(const Value *V)
Return true if the only users of this pointer are lifetime markers.
Definition: ValueTracking.cpp:4574
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:4295
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:4012
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:344
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:4915
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:5298
llvm::getIntrinsicForCallSite
Intrinsic::ID getIntrinsicForCallSite(const CallBase &CB, const TargetLibraryInfo *TLI)
Map a call instruction to an intrinsic ID.
Definition: ValueTracking.cpp:3324
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:222
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:3650
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:278
llvm::getInverseMinMaxIntrinsic
Intrinsic::ID getInverseMinMaxIntrinsic(Intrinsic::ID MinMaxID)
Definition: ValueTracking.cpp:6291
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:4739
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:3434
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:6743
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:6271
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:1174
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:5375
llvm::isGuaranteedNotToBePoison
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Definition: ValueTracking.cpp:5274
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:302
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:327
llvm::ConstantDataArraySlice::move
void move(uint64_t Delta)
Moves the Offset and adjusts Length accordingly.
Definition: ValueTracking.h:314
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:58
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:5582
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:6316
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:5414
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:4320
llvm::findAllocaForValue
AllocaInst * findAllocaForValue(Value *V, bool OffsetZero=false)
Returns unique alloca where the value comes from, or nullptr.
Definition: ValueTracking.cpp:4511
llvm::BasicBlock::const_iterator
InstListType::const_iterator const_iterator
Definition: BasicBlock.h:88
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
SmallSet.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37