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