vendor/llvm/llvm-trunk-r303571

4 files changed, 137 insertions, 52 deletions

diff --git a/include/llvm/Analysis/MemorySSA.h b/include/llvm/Analysis/MemorySSA.h
index db31ae9f4f10..f0bba8c4c020 100644
--- a/include/llvm/Analysis/MemorySSA.h
+++ b/include/llvm/Analysis/MemorySSA.h
@@ -84,6 +84,7 @@
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/PHITransAddr.h"
 #include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/DerivedUser.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/OperandTraits.h"
@@ -127,7 +128,7 @@ using const_memoryaccess_def_iterator =
 // \brief The base for all memory accesses. All memory accesses in a block are
 // linked together using an intrusive list.
 class MemoryAccess
-    : public User,
+    : public DerivedUser,
       public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>,
       public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>> {
 public:
@@ -145,15 +146,14 @@ public:
 
   MemoryAccess(const MemoryAccess &) = delete;
   MemoryAccess &operator=(const MemoryAccess &) = delete;
-  ~MemoryAccess() override;
 
   void *operator new(size_t, unsigned) = delete;
   void *operator new(size_t) = delete;
 
   BasicBlock *getBlock() const { return Block; }
 
-  virtual void print(raw_ostream &OS) const = 0;
-  virtual void dump() const;
+  void print(raw_ostream &OS) const;
+  void dump() const;
 
   /// \brief The user iterators for a memory access
   typedef user_iterator iterator;
@@ -207,11 +207,12 @@ protected:
 
   /// \brief Used for debugging and tracking things about MemoryAccesses.
   /// Guaranteed unique among MemoryAccesses, no guarantees otherwise.
-  virtual unsigned getID() const = 0;
+  inline unsigned getID() const;
 
-  MemoryAccess(LLVMContext &C, unsigned Vty, BasicBlock *BB,
-               unsigned NumOperands)
-      : User(Type::getVoidTy(C), Vty, nullptr, NumOperands), Block(BB) {}
+  MemoryAccess(LLVMContext &C, unsigned Vty, DeleteValueTy DeleteValue,
+               BasicBlock *BB, unsigned NumOperands)
+      : DerivedUser(Type::getVoidTy(C), Vty, nullptr, NumOperands, DeleteValue),
+        Block(BB) {}
 
 private:
   BasicBlock *Block;
@@ -248,21 +249,21 @@ public:
 
   // Sadly, these have to be public because they are needed in some of the
   // iterators.
-  virtual bool isOptimized() const = 0;
-  virtual MemoryAccess *getOptimized() const = 0;
-  virtual void setOptimized(MemoryAccess *) = 0;
+  inline bool isOptimized() const;
+  inline MemoryAccess *getOptimized() const;
+  inline void setOptimized(MemoryAccess *);
 
   /// \brief Reset the ID of what this MemoryUse was optimized to, causing it to
   /// be rewalked by the walker if necessary.
   /// This really should only be called by tests.
-  virtual void resetOptimized() = 0;
+  inline void resetOptimized();
 
 protected:
   friend class MemorySSA;
   friend class MemorySSAUpdater;
   MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,
-                 Instruction *MI, BasicBlock *BB)
-      : MemoryAccess(C, Vty, BB, 1), MemoryInst(MI) {
+                 DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB)
+      : MemoryAccess(C, Vty, DeleteValue, BB, 1), MemoryInst(MI) {
     setDefiningAccess(DMA);
   }
   void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false) {
@@ -292,7 +293,8 @@ public:
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
 
   MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB)
-      : MemoryUseOrDef(C, DMA, MemoryUseVal, MI, BB), OptimizedID(0) {}
+      : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB),
+        OptimizedID(0) {}
 
   // allocate space for exactly one operand
   void *operator new(size_t s) { return User::operator new(s, 1); }
@@ -302,32 +304,30 @@ public:
     return MA->getValueID() == MemoryUseVal;
   }
 
-  void print(raw_ostream &OS) const override;
+  void print(raw_ostream &OS) const;
 
-  virtual void setOptimized(MemoryAccess *DMA) override {
+  void setOptimized(MemoryAccess *DMA) {
     OptimizedID = DMA->getID();
     setOperand(0, DMA);
   }
 
-  virtual bool isOptimized() const override {
+  bool isOptimized() const {
     return getDefiningAccess() && OptimizedID == getDefiningAccess()->getID();
   }
 
-  virtual MemoryAccess *getOptimized() const override {
+  MemoryAccess *getOptimized() const {
     return getDefiningAccess();
   }
-  virtual void resetOptimized() override {
+  void resetOptimized() {
     OptimizedID = INVALID_MEMORYACCESS_ID;
   }
 
 protected:
   friend class MemorySSA;
 
-  unsigned getID() const override {
-    llvm_unreachable("MemoryUses do not have IDs");
-  }
-
 private:
+  static void deleteMe(DerivedUser *Self);
+
   unsigned int OptimizedID;
 };
 
@@ -350,8 +350,8 @@ public:
 
   MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB,
             unsigned Ver)
-      : MemoryUseOrDef(C, DMA, MemoryDefVal, MI, BB), ID(Ver),
-        Optimized(nullptr), OptimizedID(INVALID_MEMORYACCESS_ID) {}
+      : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB),
+        ID(Ver), Optimized(nullptr), OptimizedID(INVALID_MEMORYACCESS_ID) {}
 
   // allocate space for exactly one operand
   void *operator new(size_t s) { return User::operator new(s, 1); }
@@ -361,27 +361,28 @@ public:
     return MA->getValueID() == MemoryDefVal;
   }
 
-  virtual void setOptimized(MemoryAccess *MA) override {
+  void setOptimized(MemoryAccess *MA) {
     Optimized = MA;
     OptimizedID = getDefiningAccess()->getID();
   }
-  virtual MemoryAccess *getOptimized() const override { return Optimized; }
-  virtual bool isOptimized() const override {
+  MemoryAccess *getOptimized() const { return Optimized; }
+  bool isOptimized() const {
     return getOptimized() && getDefiningAccess() &&
            OptimizedID == getDefiningAccess()->getID();
   }
-  virtual void resetOptimized() override {
+  void resetOptimized() {
     OptimizedID = INVALID_MEMORYACCESS_ID;
   }
 
-  void print(raw_ostream &OS) const override;
+  void print(raw_ostream &OS) const;
 
-protected:
   friend class MemorySSA;
 
-  unsigned getID() const override { return ID; }
+  unsigned getID() const { return ID; }
 
 private:
+  static void deleteMe(DerivedUser *Self);
+
   const unsigned ID;
   MemoryAccess *Optimized;
   unsigned int OptimizedID;
@@ -432,7 +433,8 @@ public:
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
 
   MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds = 0)
-      : MemoryAccess(C, MemoryPhiVal, BB, 0), ID(Ver), ReservedSpace(NumPreds) {
+      : MemoryAccess(C, MemoryPhiVal, deleteMe, BB, 0), ID(Ver),
+        ReservedSpace(NumPreds) {
     allocHungoffUses(ReservedSpace);
   }
 
@@ -534,7 +536,9 @@ public:
     return V->getValueID() == MemoryPhiVal;
   }
 
-  void print(raw_ostream &OS) const override;
+  void print(raw_ostream &OS) const;
+
+  unsigned getID() const { return ID; }
 
 protected:
   friend class MemorySSA;
@@ -546,8 +550,6 @@ protected:
     User::allocHungoffUses(N, /* IsPhi */ true);
   }
 
-  unsigned getID() const final { return ID; }
-
 private:
   // For debugging only
   const unsigned ID;
@@ -561,8 +563,45 @@ private:
     ReservedSpace = std::max(E + E / 2, 2u);
     growHungoffUses(ReservedSpace, /* IsPhi */ true);
   }
+
+  static void deleteMe(DerivedUser *Self);
 };
 
+inline unsigned MemoryAccess::getID() const {
+  assert((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&
+         "only memory defs and phis have ids");
+  if (const auto *MD = dyn_cast<MemoryDef>(this))
+    return MD->getID();
+  return cast<MemoryPhi>(this)->getID();
+}
+
+inline bool MemoryUseOrDef::isOptimized() const {
+  if (const auto *MD = dyn_cast<MemoryDef>(this))
+    return MD->isOptimized();
+  return cast<MemoryUse>(this)->isOptimized();
+}
+
+inline MemoryAccess *MemoryUseOrDef::getOptimized() const {
+  if (const auto *MD = dyn_cast<MemoryDef>(this))
+    return MD->getOptimized();
+  return cast<MemoryUse>(this)->getOptimized();
+}
+
+inline void MemoryUseOrDef::setOptimized(MemoryAccess *MA) {
+  if (auto *MD = dyn_cast<MemoryDef>(this))
+    MD->setOptimized(MA);
+  else
+    cast<MemoryUse>(this)->setOptimized(MA);
+}
+
+inline void MemoryUseOrDef::resetOptimized() {
+  if (auto *MD = dyn_cast<MemoryDef>(this))
+    MD->resetOptimized();
+  else
+    cast<MemoryUse>(this)->resetOptimized();
+}
+
+
 template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits<2> {};
 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryPhi, MemoryAccess)
 
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index ceca6cb389a1..ac54bd4cfffb 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -656,10 +656,12 @@ private:
     /// Test whether this BackedgeTakenInfo contains complete information.
     bool hasFullInfo() const { return isComplete(); }
 
-    /// Return an expression indicating the exact backedge-taken count of the
-    /// loop if it is known or SCEVCouldNotCompute otherwise. This is the
-    /// number of times the loop header can be guaranteed to execute, minus
-    /// one.
+    /// Return an expression indicating the exact *backedge-taken*
+    /// count of the loop if it is known or SCEVCouldNotCompute
+    /// otherwise.  If execution makes it to the backedge on every
+    /// iteration (i.e. there are no abnormal exists like exception
+    /// throws and thread exits) then this is the number of times the
+    /// loop header will execute minus one.
     ///
     /// If the SCEV predicate associated with the answer can be different
     /// from AlwaysTrue, we must add a (non null) Predicates argument.
@@ -1398,11 +1400,11 @@ public:
   const SCEV *getExitCount(const Loop *L, BasicBlock *ExitingBlock);
 
   /// If the specified loop has a predictable backedge-taken count, return it,
-  /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count
-  /// is the number of times the loop header will be branched to from within
-  /// the loop. This is one less than the trip count of the loop, since it
-  /// doesn't count the first iteration, when the header is branched to from
-  /// outside the loop.
+  /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is
+  /// the number of times the loop header will be branched to from within the
+  /// loop, assuming there are no abnormal exists like exception throws. This is
+  /// one less than the trip count of the loop, since it doesn't count the first
+  /// iteration, when the header is branched to from outside the loop.
   ///
   /// Note that it is not valid to call this method on a loop without a
   /// loop-invariant backedge-taken count (see
@@ -1417,8 +1419,10 @@ public:
   const SCEV *getPredicatedBackedgeTakenCount(const Loop *L,
                                               SCEVUnionPredicate &Predicates);
 
-  /// Similar to getBackedgeTakenCount, except return the least SCEV value
-  /// that is known never to be less than the actual backedge taken count.
+  /// When successful, this returns a SCEVConstant that is greater than or equal
+  /// to (i.e. a "conservative over-approximation") of the value returend by
+  /// getBackedgeTakenCount.  If such a value cannot be computed, it returns the
+  /// SCEVCouldNotCompute object.
   const SCEV *getMaxBackedgeTakenCount(const Loop *L);
 
   /// Return true if the backedge taken count is either the value returned by
diff --git a/include/llvm/Analysis/TargetLibraryInfo.h b/include/llvm/Analysis/TargetLibraryInfo.h
index 944250cfd6ac..0e3bdaa11c9a 100644
--- a/include/llvm/Analysis/TargetLibraryInfo.h
+++ b/include/llvm/Analysis/TargetLibraryInfo.h
@@ -191,6 +191,14 @@ public:
   void setShouldSignExtI32Param(bool Val) {
     ShouldSignExtI32Param = Val;
   }
+
+  /// Returns the size of the wchar_t type in bytes.
+  unsigned getWCharSize(const Module &M) const;
+
+  /// Returns size of the default wchar_t type on target \p T. This is mostly
+  /// intended to verify that the size in the frontend matches LLVM. All other
+  /// queries should use getWCharSize() instead.
+  static unsigned getTargetWCharSize(const Triple &T);
 };
 
 /// Provides information about what library functions are available for
@@ -307,6 +315,11 @@ public:
     return Attribute::None;
   }
 
+  /// \copydoc TargetLibraryInfoImpl::getWCharSize()
+  unsigned getWCharSize(const Module &M) const {
+    return Impl->getWCharSize(M);
+  }
+
   /// Handle invalidation from the pass manager.
   ///
   /// If we try to invalidate this info, just return false. It cannot become
diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h
index f5f323c6b797..cf24062e46f8 100644
--- a/include/llvm/Analysis/ValueTracking.h
+++ b/include/llvm/Analysis/ValueTracking.h
@@ -218,9 +218,38 @@ template <typename T> class ArrayRef;
                                             DL);
   }
 
-  /// Returns true if the GEP is based on a pointer to a string (array of i8), 
-  /// and is indexing into this string.
-  bool isGEPBasedOnPointerToString(const GEPOperator *GEP);
+  /// Returns true if the GEP is based on a pointer to a string (array of
+  // \p CharSize integers) and is indexing into this string.
+  bool isGEPBasedOnPointerToString(const GEPOperator *GEP,
+                                   unsigned CharSize = 8);
+
+  /// Represents offset+length into a ConstantDataArray.
+  struct ConstantDataArraySlice {
+    /// ConstantDataArray pointer. nullptr indicates a zeroinitializer (a valid
+    /// initializer, it just doesn't fit the ConstantDataArray interface).
+    const ConstantDataArray *Array;
+    /// Slice starts at this Offset.
+    uint64_t Offset;
+    /// Length of the slice.
+    uint64_t Length;
+
+    /// Moves the Offset and adjusts Length accordingly.
+    void move(uint64_t Delta) {
+      assert(Delta < Length);
+      Offset += Delta;
+      Length -= Delta;
+    }
+    /// Convenience accessor for elements in the slice.
+    uint64_t operator[](unsigned I) const {
+      return Array==nullptr ? 0 : Array->getElementAsInteger(I + Offset);
+    }
+  };
+
+  /// Returns true if the value \p V is a pointer into a ContantDataArray.
+  /// If successfull \p Index will point to a ConstantDataArray info object
+  /// with an apropriate offset.
+  bool getConstantDataArrayInfo(const Value *V, ConstantDataArraySlice &Slice,
+                                unsigned ElementSize, uint64_t Offset = 0);
 
   /// This function computes the length of a null-terminated C string pointed to
   /// by V. If successful, it returns true and returns the string in Str. If
@@ -233,7 +262,7 @@ template <typename T> class ArrayRef;
 
   /// If we can compute the length of the string pointed to by the specified
   /// pointer, return 'len+1'.  If we can't, return 0.
-  uint64_t GetStringLength(const Value *V);
+  uint64_t GetStringLength(const Value *V, unsigned CharSize = 8);
 
   /// This method strips off any GEP address adjustments and pointer casts from
   /// the specified value, returning the original object being addressed. Note