vendor/llvm/llvm-trunk-r238337

1 files changed, 124 insertions, 33 deletions

diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h
index cc588381727d..653821d02271 100644
--- a/include/llvm/Analysis/ValueTracking.h
+++ b/include/llvm/Analysis/ValueTracking.h
@@ -16,6 +16,7 @@
 #define LLVM_ANALYSIS_VALUETRACKING_H
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/IR/Instruction.h"
 #include "llvm/Support/DataTypes.h"
 
 namespace llvm {
@@ -28,17 +29,18 @@ namespace llvm {
   class AssumptionCache;
   class DominatorTree;
   class TargetLibraryInfo;
+  class LoopInfo;
 
   /// Determine which bits of V are known to be either zero or one and return
   /// them in the KnownZero/KnownOne bit sets.
   ///
   /// This function is defined on values with integer type, values with pointer
-  /// type (but only if TD is non-null), and vectors of integers.  In the case
+  /// type, and vectors of integers.  In the case
   /// where V is a vector, the known zero and known one values are the
   /// same width as the vector element, and the bit is set only if it is true
   /// for all of the elements in the vector.
   void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
-                        const DataLayout *TD = nullptr, unsigned Depth = 0,
+                        const DataLayout &DL, unsigned Depth = 0,
                         AssumptionCache *AC = nullptr,
                         const Instruction *CxtI = nullptr,
                         const DominatorTree *DT = nullptr);
@@ -46,11 +48,16 @@ namespace llvm {
   /// \p KnownZero the set of bits that are known to be zero
   void computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
                                          APInt &KnownZero);
+  /// Returns true if LHS and RHS have no common bits set.
+  bool haveNoCommonBitsSet(Value *LHS, Value *RHS, const DataLayout &DL,
+                           AssumptionCache *AC = nullptr,
+                           const Instruction *CxtI = nullptr,
+                           const DominatorTree *DT = nullptr);
 
   /// ComputeSignBit - Determine whether the sign bit is known to be zero or
   /// one.  Convenience wrapper around computeKnownBits.
   void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne,
-                      const DataLayout *TD = nullptr, unsigned Depth = 0,
+                      const DataLayout &DL, unsigned Depth = 0,
                       AssumptionCache *AC = nullptr,
                       const Instruction *CxtI = nullptr,
                       const DominatorTree *DT = nullptr);
@@ -60,7 +67,8 @@ namespace llvm {
   /// element is known to be a power of two when defined.  Supports values with
   /// integer or pointer type and vectors of integers.  If 'OrZero' is set then
   /// returns true if the given value is either a power of two or zero.
-  bool isKnownToBeAPowerOfTwo(Value *V, bool OrZero = false, unsigned Depth = 0,
+  bool isKnownToBeAPowerOfTwo(Value *V, const DataLayout &DL,
+                              bool OrZero = false, unsigned Depth = 0,
                               AssumptionCache *AC = nullptr,
                               const Instruction *CxtI = nullptr,
                               const DominatorTree *DT = nullptr);
@@ -69,8 +77,8 @@ namespace llvm {
   /// when defined.  For vectors return true if every element is known to be
   /// non-zero when defined.  Supports values with integer or pointer type and
   /// vectors of integers.
-  bool isKnownNonZero(Value *V, const DataLayout *TD = nullptr,
-                      unsigned Depth = 0, AssumptionCache *AC = nullptr,
+  bool isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth = 0,
+                      AssumptionCache *AC = nullptr,
                       const Instruction *CxtI = nullptr,
                       const DominatorTree *DT = nullptr);
 
@@ -79,13 +87,12 @@ namespace llvm {
   /// zero for bits that V cannot have.
   ///
   /// This function is defined on values with integer type, values with pointer
-  /// type (but only if TD is non-null), and vectors of integers.  In the case
+  /// type, and vectors of integers.  In the case
   /// where V is a vector, the mask, known zero, and known one values are the
   /// same width as the vector element, and the bit is set only if it is true
   /// for all of the elements in the vector.
-  bool MaskedValueIsZero(Value *V, const APInt &Mask,
-                         const DataLayout *TD = nullptr, unsigned Depth = 0,
-                         AssumptionCache *AC = nullptr,
+  bool MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout &DL,
+                         unsigned Depth = 0, AssumptionCache *AC = nullptr,
                          const Instruction *CxtI = nullptr,
                          const DominatorTree *DT = nullptr);
 
@@ -97,7 +104,7 @@ namespace llvm {
   ///
   /// 'Op' must have a scalar integer type.
   ///
-  unsigned ComputeNumSignBits(Value *Op, const DataLayout *TD = nullptr,
+  unsigned ComputeNumSignBits(Value *Op, const DataLayout &DL,
                               unsigned Depth = 0, AssumptionCache *AC = nullptr,
                               const Instruction *CxtI = nullptr,
                               const DominatorTree *DT = nullptr);
@@ -116,6 +123,11 @@ namespace llvm {
   ///
   bool CannotBeNegativeZero(const Value *V, unsigned Depth = 0);
 
+  /// CannotBeOrderedLessThanZero - Return true if we can prove that the 
+  /// specified FP value is either a NaN or never less than 0.0.
+  ///
+  bool CannotBeOrderedLessThanZero(const Value *V, unsigned Depth = 0);
+
   /// isBytewiseValue - If the specified value can be set by repeating the same
   /// byte in memory, return the i8 value that it is represented with.  This is
   /// true for all i8 values obviously, but is also true for i32 0, i32 -1,
@@ -137,11 +149,12 @@ namespace llvm {
   /// it can be expressed as a base pointer plus a constant offset.  Return the
   /// base and offset to the caller.
   Value *GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset,
-                                          const DataLayout *TD);
+                                          const DataLayout &DL);
   static inline const Value *
   GetPointerBaseWithConstantOffset(const Value *Ptr, int64_t &Offset,
-                                   const DataLayout *TD) {
-    return GetPointerBaseWithConstantOffset(const_cast<Value*>(Ptr), Offset,TD);
+                                   const DataLayout &DL) {
+    return GetPointerBaseWithConstantOffset(const_cast<Value *>(Ptr), Offset,
+                                            DL);
   }
   
   /// getConstantStringInfo - This function computes the length of a
@@ -162,26 +175,59 @@ namespace llvm {
   /// being addressed.  Note that the returned value has pointer type if the
   /// specified value does.  If the MaxLookup value is non-zero, it limits the
   /// number of instructions to be stripped off.
-  Value *GetUnderlyingObject(Value *V, const DataLayout *TD = nullptr,
+  Value *GetUnderlyingObject(Value *V, const DataLayout &DL,
                              unsigned MaxLookup = 6);
-  static inline const Value *
-  GetUnderlyingObject(const Value *V, const DataLayout *TD = nullptr,
-                      unsigned MaxLookup = 6) {
-    return GetUnderlyingObject(const_cast<Value *>(V), TD, MaxLookup);
+  static inline const Value *GetUnderlyingObject(const Value *V,
+                                                 const DataLayout &DL,
+                                                 unsigned MaxLookup = 6) {
+    return GetUnderlyingObject(const_cast<Value *>(V), DL, MaxLookup);
   }
 
-  /// GetUnderlyingObjects - This method is similar to GetUnderlyingObject
-  /// except that it can look through phi and select instructions and return
-  /// multiple objects.
-  void GetUnderlyingObjects(Value *V,
-                            SmallVectorImpl<Value *> &Objects,
-                            const DataLayout *TD = nullptr,
+  /// \brief This method is similar to GetUnderlyingObject except that it can
+  /// look through phi and select instructions and return multiple objects.
+  ///
+  /// If LoopInfo is passed, loop phis are further analyzed.  If a pointer
+  /// accesses different objects in each iteration, we don't look through the
+  /// phi node. E.g. consider this loop nest:
+  ///
+  ///   int **A;
+  ///   for (i)
+  ///     for (j) {
+  ///        A[i][j] = A[i-1][j] * B[j]
+  ///     }
+  ///
+  /// This is transformed by Load-PRE to stash away A[i] for the next iteration
+  /// of the outer loop:
+  ///
+  ///   Curr = A[0];          // Prev_0
+  ///   for (i: 1..N) {
+  ///     Prev = Curr;        // Prev = PHI (Prev_0, Curr)
+  ///     Curr = A[i];
+  ///     for (j: 0..N) {
+  ///        Curr[j] = Prev[j] * B[j]
+  ///     }
+  ///   }
+  ///
+  /// Since A[i] and A[i-1] are independent pointers, getUnderlyingObjects
+  /// should not assume that Curr and Prev share the same underlying object thus
+  /// it shouldn't look through the phi above.
+  void GetUnderlyingObjects(Value *V, SmallVectorImpl<Value *> &Objects,
+                            const DataLayout &DL, LoopInfo *LI = nullptr,
                             unsigned MaxLookup = 6);
 
   /// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer
   /// are lifetime markers.
   bool onlyUsedByLifetimeMarkers(const Value *V);
 
+  /// isDereferenceablePointer - Return true if this is always a dereferenceable
+  /// pointer. If the context instruction is specified perform context-sensitive
+  /// analysis and return true if the pointer is dereferenceable at the
+  /// specified instruction.
+  bool isDereferenceablePointer(const Value *V, const DataLayout &DL,
+                                const Instruction *CtxI = nullptr,
+                                const DominatorTree *DT = nullptr,
+                                const TargetLibraryInfo *TLI = nullptr);
+  
   /// isSafeToSpeculativelyExecute - Return true if the instruction does not
   /// have any effects besides calculating the result and does not have
   /// undefined behavior.
@@ -195,37 +241,82 @@ namespace llvm {
   /// memory leak. It also returns false for instructions related to control
   /// flow, specifically terminators and PHI nodes.
   ///
-  /// This method only looks at the instruction itself and its operands, so if
-  /// this method returns true, it is safe to move the instruction as long as
-  /// the correct dominance relationships for the operands and users hold.
-  /// However, this method can return true for instructions that read memory;
+  /// If the CtxI is specified this method performs context-sensitive analysis
+  /// and returns true if it is safe to execute the instruction immediately
+  /// before the CtxI.
+  ///
+  /// If the CtxI is NOT specified this method only looks at the instruction
+  /// itself and its operands, so if this method returns true, it is safe to
+  /// move the instruction as long as the correct dominance relationships for
+  /// the operands and users hold.
+  ///
+  /// This method can return true for instructions that read memory;
   /// for such instructions, moving them may change the resulting value.
   bool isSafeToSpeculativelyExecute(const Value *V,
-                                    const DataLayout *TD = nullptr);
+                                    const Instruction *CtxI = nullptr,
+                                    const DominatorTree *DT = nullptr,
+                                    const TargetLibraryInfo *TLI = nullptr);
 
   /// isKnownNonNull - Return true if this pointer couldn't possibly be null by
   /// its definition.  This returns true for allocas, non-extern-weak globals
   /// and byval arguments.
   bool isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI = nullptr);
 
+  /// isKnownNonNullAt - Return true if this pointer couldn't possibly be null.
+  /// If the context instruction is specified perform context-sensitive analysis
+  /// and return true if the pointer couldn't possibly be null at the specified
+  /// instruction.
+  bool isKnownNonNullAt(const Value *V,
+                        const Instruction *CtxI = nullptr,
+                        const DominatorTree *DT  = nullptr,
+                        const TargetLibraryInfo *TLI = nullptr);
+
   /// Return true if it is valid to use the assumptions provided by an
   /// assume intrinsic, I, at the point in the control-flow identified by the
   /// context instruction, CxtI.
   bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI,
-                               const DataLayout *DL = nullptr,
                                const DominatorTree *DT = nullptr);
 
   enum class OverflowResult { AlwaysOverflows, MayOverflow, NeverOverflows };
   OverflowResult computeOverflowForUnsignedMul(Value *LHS, Value *RHS,
-                                               const DataLayout *DL,
+                                               const DataLayout &DL,
                                                AssumptionCache *AC,
                                                const Instruction *CxtI,
                                                const DominatorTree *DT);
   OverflowResult computeOverflowForUnsignedAdd(Value *LHS, Value *RHS,
-                                               const DataLayout *DL,
+                                               const DataLayout &DL,
                                                AssumptionCache *AC,
                                                const Instruction *CxtI,
                                                const DominatorTree *DT);
+  
+  /// \brief Specific patterns of select instructions we can match.
+  enum SelectPatternFlavor {
+    SPF_UNKNOWN = 0,
+    SPF_SMIN,                   // Signed minimum
+    SPF_UMIN,                   // Unsigned minimum
+    SPF_SMAX,                   // Signed maximum
+    SPF_UMAX,                   // Unsigned maximum
+    SPF_ABS,                    // Absolute value
+    SPF_NABS                    // Negated absolute value
+  };
+  /// Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind
+  /// and providing the out parameter results if we successfully match.
+  ///
+  /// If CastOp is not nullptr, also match MIN/MAX idioms where the type does
+  /// not match that of the original select. If this is the case, the cast
+  /// operation (one of Trunc,SExt,Zext) that must be done to transform the
+  /// type of LHS and RHS into the type of V is returned in CastOp.
+  ///
+  /// For example:
+  ///   %1 = icmp slt i32 %a, i32 4
+  ///   %2 = sext i32 %a to i64
+  ///   %3 = select i1 %1, i64 %2, i64 4
+  ///
+  /// -> LHS = %a, RHS = i32 4, *CastOp = Instruction::SExt
+  ///
+  SelectPatternFlavor matchSelectPattern(Value *V, Value *&LHS, Value *&RHS,
+                                         Instruction::CastOps *CastOp = nullptr);
+
 } // end namespace llvm
 
 #endif