LCOV - code coverage report
Current view: top level - include/llvm/Analysis - ValueTracking.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 15 15 100.0 %
Date: 2018-07-13 00:08:38 Functions: 2 2 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13