vendor/llvm/llvm-release_360-r226102

34 files changed, 691 insertions, 417 deletions

diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h
index 689766446445..763f37298811 100644
--- a/include/llvm/Analysis/AliasAnalysis.h
+++ b/include/llvm/Analysis/AliasAnalysis.h
@@ -39,6 +39,7 @@
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/IR/CallSite.h"
+#include "llvm/IR/Metadata.h"
 
 namespace llvm {
 
@@ -112,13 +113,14 @@ public:
     /// there are restrictions on stepping out of one object and into another.
     /// See http://llvm.org/docs/LangRef.html#pointeraliasing
     uint64_t Size;
-    /// TBAATag - The metadata node which describes the TBAA type of
-    /// the location, or null if there is no known unique tag.
-    const MDNode *TBAATag;
+    /// AATags - The metadata nodes which describes the aliasing of the
+    /// location (each member is null if that kind of information is
+    /// unavailable)..
+    AAMDNodes AATags;
 
     explicit Location(const Value *P = nullptr, uint64_t S = UnknownSize,
-                      const MDNode *N = nullptr)
-      : Ptr(P), Size(S), TBAATag(N) {}
+                      const AAMDNodes &N = AAMDNodes())
+      : Ptr(P), Size(S), AATags(N) {}
 
     Location getWithNewPtr(const Value *NewPtr) const {
       Location Copy(*this);
@@ -132,9 +134,9 @@ public:
       return Copy;
     }
 
-    Location getWithoutTBAATag() const {
+    Location getWithoutAATags() const {
       Location Copy(*this);
-      Copy.TBAATag = nullptr;
+      Copy.AATags = AAMDNodes();
       return Copy;
     }
   };
@@ -500,7 +502,7 @@ public:
   ///
 
   /// canBasicBlockModify - Return true if it is possible for execution of the
-  /// specified basic block to modify the value pointed to by Ptr.
+  /// specified basic block to modify the location Loc.
   bool canBasicBlockModify(const BasicBlock &BB, const Location &Loc);
 
   /// canBasicBlockModify - A convenience wrapper.
@@ -508,17 +510,20 @@ public:
     return canBasicBlockModify(BB, Location(P, Size));
   }
 
-  /// canInstructionRangeModify - Return true if it is possible for the
-  /// execution of the specified instructions to modify the value pointed to by
-  /// Ptr.  The instructions to consider are all of the instructions in the
-  /// range of [I1,I2] INCLUSIVE.  I1 and I2 must be in the same basic block.
-  bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2,
-                                 const Location &Loc);
+  /// canInstructionRangeModRef - Return true if it is possible for the
+  /// execution of the specified instructions to mod\ref (according to the
+  /// mode) the location Loc. The instructions to consider are all
+  /// of the instructions in the range of [I1,I2] INCLUSIVE.
+  /// I1 and I2 must be in the same basic block.
+  bool canInstructionRangeModRef(const Instruction &I1,
+                                const Instruction &I2, const Location &Loc,
+                                const ModRefResult Mode);
 
-  /// canInstructionRangeModify - A convenience wrapper.
-  bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2,
-                                 const Value *Ptr, uint64_t Size) {
-    return canInstructionRangeModify(I1, I2, Location(Ptr, Size));
+  /// canInstructionRangeModRef - A convenience wrapper.
+  bool canInstructionRangeModRef(const Instruction &I1,
+                                 const Instruction &I2, const Value *Ptr,
+                                 uint64_t Size, const ModRefResult Mode) {
+    return canInstructionRangeModRef(I1, I2, Location(Ptr, Size), Mode);
   }
 
   //===--------------------------------------------------------------------===//
@@ -566,25 +571,23 @@ public:
 template<>
 struct DenseMapInfo<AliasAnalysis::Location> {
   static inline AliasAnalysis::Location getEmptyKey() {
-    return
-      AliasAnalysis::Location(DenseMapInfo<const Value *>::getEmptyKey(),
-                              0, nullptr);
+    return AliasAnalysis::Location(DenseMapInfo<const Value *>::getEmptyKey(),
+                                   0);
   }
   static inline AliasAnalysis::Location getTombstoneKey() {
-    return
-      AliasAnalysis::Location(DenseMapInfo<const Value *>::getTombstoneKey(),
-                              0, nullptr);
+    return AliasAnalysis::Location(
+        DenseMapInfo<const Value *>::getTombstoneKey(), 0);
   }
   static unsigned getHashValue(const AliasAnalysis::Location &Val) {
     return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^
            DenseMapInfo<uint64_t>::getHashValue(Val.Size) ^
-           DenseMapInfo<const MDNode *>::getHashValue(Val.TBAATag);
+           DenseMapInfo<AAMDNodes>::getHashValue(Val.AATags);
   }
   static bool isEqual(const AliasAnalysis::Location &LHS,
                       const AliasAnalysis::Location &RHS) {
     return LHS.Ptr == RHS.Ptr &&
            LHS.Size == RHS.Size &&
-           LHS.TBAATag == RHS.TBAATag;
+           LHS.AATags == RHS.AATags;
   }
 };
 
diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h
index e32b6d628b7f..036d58dfa810 100644
--- a/include/llvm/Analysis/AliasSetTracker.h
+++ b/include/llvm/Analysis/AliasSetTracker.h
@@ -20,6 +20,7 @@
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/ilist.h"
 #include "llvm/ADT/ilist_node.h"
+#include "llvm/IR/Metadata.h"
 #include "llvm/IR/ValueHandle.h"
 #include <vector>
 
@@ -40,11 +41,11 @@ class AliasSet : public ilist_node<AliasSet> {
     PointerRec **PrevInList, *NextInList;
     AliasSet *AS;
     uint64_t Size;
-    const MDNode *TBAAInfo;
+    AAMDNodes AAInfo;
   public:
     PointerRec(Value *V)
       : Val(V), PrevInList(nullptr), NextInList(nullptr), AS(nullptr), Size(0),
-        TBAAInfo(DenseMapInfo<const MDNode *>::getEmptyKey()) {}
+        AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {}
 
     Value *getValue() const { return Val; }
     
@@ -56,27 +57,27 @@ class AliasSet : public ilist_node<AliasSet> {
       return &NextInList;
     }
 
-    void updateSizeAndTBAAInfo(uint64_t NewSize, const MDNode *NewTBAAInfo) {
+    void updateSizeAndAAInfo(uint64_t NewSize, const AAMDNodes &NewAAInfo) {
       if (NewSize > Size) Size = NewSize;
 
-      if (TBAAInfo == DenseMapInfo<const MDNode *>::getEmptyKey())
-        // We don't have a TBAAInfo yet. Set it to NewTBAAInfo.
-        TBAAInfo = NewTBAAInfo;
-      else if (TBAAInfo != NewTBAAInfo)
-        // NewTBAAInfo conflicts with TBAAInfo.
-        TBAAInfo = DenseMapInfo<const MDNode *>::getTombstoneKey();
+      if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
+        // We don't have a AAInfo yet. Set it to NewAAInfo.
+        AAInfo = NewAAInfo;
+      else if (AAInfo != NewAAInfo)
+        // NewAAInfo conflicts with AAInfo.
+        AAInfo = DenseMapInfo<AAMDNodes>::getTombstoneKey();
     }
 
     uint64_t getSize() const { return Size; }
 
-    /// getTBAAInfo - Return the TBAAInfo, or null if there is no
+    /// getAAInfo - Return the AAInfo, or null if there is no
     /// information or conflicting information.
-    const MDNode *getTBAAInfo() const {
-      // If we have missing or conflicting TBAAInfo, return null.
-      if (TBAAInfo == DenseMapInfo<const MDNode *>::getEmptyKey() ||
-          TBAAInfo == DenseMapInfo<const MDNode *>::getTombstoneKey())
-        return nullptr;
-      return TBAAInfo;
+    AAMDNodes getAAInfo() const {
+      // If we have missing or conflicting AAInfo, return null.
+      if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey() ||
+          AAInfo == DenseMapInfo<AAMDNodes>::getTombstoneKey())
+        return AAMDNodes();
+      return AAInfo;
     }
 
     AliasSet *getAliasSet(AliasSetTracker &AST) {
@@ -204,7 +205,7 @@ public:
 
     Value *getPointer() const { return CurNode->getValue(); }
     uint64_t getSize() const { return CurNode->getSize(); }
-    const MDNode *getTBAAInfo() const { return CurNode->getTBAAInfo(); }
+    AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); }
 
     iterator& operator++() {                // Preincrement
       assert(CurNode && "Advancing past AliasSet.end()!");
@@ -250,7 +251,7 @@ private:
   void removeFromTracker(AliasSetTracker &AST);
 
   void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size,
-                  const MDNode *TBAAInfo,
+                  const AAMDNodes &AAInfo,
                   bool KnownMustAlias = false);
   void addUnknownInst(Instruction *I, AliasAnalysis &AA);
   void removeUnknownInst(AliasSetTracker &AST, Instruction *I) {
@@ -270,7 +271,7 @@ public:
   /// aliasesPointer - Return true if the specified pointer "may" (or must)
   /// alias one of the members in the set.
   ///
-  bool aliasesPointer(const Value *Ptr, uint64_t Size, const MDNode *TBAAInfo,
+  bool aliasesPointer(const Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo,
                       AliasAnalysis &AA) const;
   bool aliasesUnknownInst(Instruction *Inst, AliasAnalysis &AA) const;
 };
@@ -325,7 +326,7 @@ public:
   /// These methods return true if inserting the instruction resulted in the
   /// addition of a new alias set (i.e., the pointer did not alias anything).
   ///
-  bool add(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo); // Add a location
+  bool add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo); // Add a loc.
   bool add(LoadInst *LI);
   bool add(StoreInst *SI);
   bool add(VAArgInst *VAAI);
@@ -338,7 +339,7 @@ public:
   /// be aliased by the specified instruction.  These methods return true if any
   /// alias sets were eliminated.
   // Remove a location
-  bool remove(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo);
+  bool remove(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo);
   bool remove(LoadInst *LI);
   bool remove(StoreInst *SI);
   bool remove(VAArgInst *VAAI);
@@ -357,20 +358,24 @@ public:
   /// true if a new alias set is created to contain the pointer (because the
   /// pointer didn't alias anything).
   AliasSet &getAliasSetForPointer(Value *P, uint64_t Size,
-                                  const MDNode *TBAAInfo,
+                                  const AAMDNodes &AAInfo,
                                   bool *New = nullptr);
 
   /// getAliasSetForPointerIfExists - Return the alias set containing the
   /// location specified if one exists, otherwise return null.
   AliasSet *getAliasSetForPointerIfExists(Value *P, uint64_t Size,
-                                          const MDNode *TBAAInfo) {
-    return findAliasSetForPointer(P, Size, TBAAInfo);
+                                          const AAMDNodes &AAInfo) {
+    return findAliasSetForPointer(P, Size, AAInfo);
   }
 
   /// containsPointer - Return true if the specified location is represented by
   /// this alias set, false otherwise.  This does not modify the AST object or
   /// alias sets.
-  bool containsPointer(Value *P, uint64_t Size, const MDNode *TBAAInfo) const;
+  bool containsPointer(Value *P, uint64_t Size, const AAMDNodes &AAInfo) const;
+
+  /// Return true if the specified instruction "may" (or must) alias one of the
+  /// members in any of the sets.
+  bool containsUnknown(Instruction *I) const;
 
   /// getAliasAnalysis - Return the underlying alias analysis object used by
   /// this tracker.
@@ -417,16 +422,16 @@ private:
     return *Entry;
   }
 
-  AliasSet &addPointer(Value *P, uint64_t Size, const MDNode *TBAAInfo,
+  AliasSet &addPointer(Value *P, uint64_t Size, const AAMDNodes &AAInfo,
                        AliasSet::AccessType E,
                        bool &NewSet) {
     NewSet = false;
-    AliasSet &AS = getAliasSetForPointer(P, Size, TBAAInfo, &NewSet);
+    AliasSet &AS = getAliasSetForPointer(P, Size, AAInfo, &NewSet);
     AS.AccessTy |= E;
     return AS;
   }
   AliasSet *findAliasSetForPointer(const Value *Ptr, uint64_t Size,
-                                   const MDNode *TBAAInfo);
+                                   const AAMDNodes &AAInfo);
 
   AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
 };
diff --git a/include/llvm/Analysis/AssumptionCache.h b/include/llvm/Analysis/AssumptionCache.h
new file mode 100644
index 000000000000..b129e6796328
--- /dev/null
+++ b/include/llvm/Analysis/AssumptionCache.h
@@ -0,0 +1,142 @@
+//===- llvm/Analysis/AssumptionCache.h - Track @llvm.assume ---*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains a pass that keeps track of @llvm.assume intrinsics in
+// the functions of a module (allowing assumptions within any function to be
+// found cheaply by other parts of the optimizer).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ASSUMPTIONCACHE_H
+#define LLVM_ANALYSIS_ASSUMPTIONCACHE_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/Pass.h"
+#include <memory>
+
+namespace llvm {
+
+/// \brief A cache of @llvm.assume calls within a function.
+///
+/// This cache provides fast lookup of assumptions within a function by caching
+/// them and amortizing the cost of scanning for them across all queries. The
+/// cache is also conservatively self-updating so that it will never return
+/// incorrect results about a function even as the function is being mutated.
+/// However, flushing the cache and rebuilding it (or explicitly updating it)
+/// may allow it to discover new assumptions.
+class AssumptionCache {
+  /// \brief The function for which this cache is handling assumptions.
+  ///
+  /// We track this to lazily populate our assumptions.
+  Function &F;
+
+  /// \brief Vector of weak value handles to calls of the @llvm.assume
+  /// intrinsic.
+  SmallVector<WeakVH, 4> AssumeHandles;
+
+  /// \brief Flag tracking whether we have scanned the function yet.
+  ///
+  /// We want to be as lazy about this as possible, and so we scan the function
+  /// at the last moment.
+  bool Scanned;
+
+  /// \brief Scan the function for assumptions and add them to the cache.
+  void scanFunction();
+
+public:
+  /// \brief Construct an AssumptionCache from a function by scanning all of
+  /// its instructions.
+  AssumptionCache(Function &F) : F(F), Scanned(false) {}
+
+  /// \brief Add an @llvm.assume intrinsic to this function's cache.
+  ///
+  /// The call passed in must be an instruction within this fuction and must
+  /// not already be in the cache.
+  void registerAssumption(CallInst *CI);
+
+  /// \brief Clear the cache of @llvm.assume intrinsics for a function.
+  ///
+  /// It will be re-scanned the next time it is requested.
+  void clear() {
+    AssumeHandles.clear();
+    Scanned = false;
+  }
+
+  /// \brief Access the list of assumption handles currently tracked for this
+  /// fuction.
+  ///
+  /// Note that these produce weak handles that may be null. The caller must
+  /// handle that case.
+  /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
+  /// when we can write that to filter out the null values. Then caller code
+  /// will become simpler.
+  MutableArrayRef<WeakVH> assumptions() {
+    if (!Scanned)
+      scanFunction();
+    return AssumeHandles;
+  }
+};
+
+/// \brief An immutable pass that tracks lazily created \c AssumptionCache
+/// objects.
+///
+/// This is essentially a workaround for the legacy pass manager's weaknesses
+/// which associates each assumption cache with Function and clears it if the
+/// function is deleted. The nature of the AssumptionCache is that it is not
+/// invalidated by any changes to the function body and so this is sufficient
+/// to be conservatively correct.
+class AssumptionCacheTracker : public ImmutablePass {
+  /// A callback value handle applied to function objects, which we use to
+  /// delete our cache of intrinsics for a function when it is deleted.
+  class FunctionCallbackVH : public CallbackVH {
+    AssumptionCacheTracker *ACT;
+    void deleted() override;
+
+  public:
+    typedef DenseMapInfo<Value *> DMI;
+
+    FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
+        : CallbackVH(V), ACT(ACT) {}
+  };
+
+  friend FunctionCallbackVH;
+
+  typedef DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>,
+                   FunctionCallbackVH::DMI> FunctionCallsMap;
+  FunctionCallsMap AssumptionCaches;
+
+public:
+  /// \brief Get the cached assumptions for a function.
+  ///
+  /// If no assumptions are cached, this will scan the function. Otherwise, the
+  /// existing cache will be returned.
+  AssumptionCache &getAssumptionCache(Function &F);
+
+  AssumptionCacheTracker();
+  ~AssumptionCacheTracker();
+
+  void releaseMemory() override { AssumptionCaches.shrink_and_clear(); }
+
+  void verifyAnalysis() const override;
+  bool doFinalization(Module &) override {
+    verifyAnalysis();
+    return false;
+  }
+
+  static char ID; // Pass identification, replacement for typeid
+};
+
+} // end namespace llvm
+
+#endif
diff --git a/include/llvm/Analysis/BlockFrequencyInfoImpl.h b/include/llvm/Analysis/BlockFrequencyInfoImpl.h
index bb256c7bbcc8..57b515420925 100644
--- a/include/llvm/Analysis/BlockFrequencyInfoImpl.h
+++ b/include/llvm/Analysis/BlockFrequencyInfoImpl.h
@@ -260,7 +260,7 @@ public:
     /// loop.
     ///
     /// This function should only be called when distributing mass.  As long as
-    /// there are no irreducilbe edges to Node, then it will have complexity
+    /// there are no irreducible edges to Node, then it will have complexity
     /// O(1) in this context.
     ///
     /// In general, the complexity is O(L), where L is the number of loop
diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h
index 4414c84f6b7a..89eef68d8431 100644
--- a/include/llvm/Analysis/BranchProbabilityInfo.h
+++ b/include/llvm/Analysis/BranchProbabilityInfo.h
@@ -111,6 +111,10 @@ public:
   void setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors,
                      uint32_t Weight);
 
+  static uint32_t getBranchWeightStackProtector(bool IsLikely) {
+    return IsLikely ? (1u << 20) - 1 : 1;
+  }
+
 private:
   // Since we allow duplicate edges from one basic block to another, we use
   // a pair (PredBlock and an index in the successors) to specify an edge.
diff --git a/include/llvm/Analysis/CFGPrinter.h b/include/llvm/Analysis/CFGPrinter.h
index e6d2ed1a6864..035764837e6f 100644
--- a/include/llvm/Analysis/CFGPrinter.h
+++ b/include/llvm/Analysis/CFGPrinter.h
@@ -72,13 +72,13 @@ struct DOTGraphTraits<const Function*> : public DefaultDOTGraphTraits {
         OutStr.erase(OutStr.begin()+i, OutStr.begin()+Idx);
         --i;
       } else if (ColNum == MaxColumns) {                  // Wrap lines.
-        if (LastSpace) {
-          OutStr.insert(LastSpace, "\\l...");
-          ColNum = i - LastSpace;
-          LastSpace = 0;
-          i += 3; // The loop will advance 'i' again.
-        }
-        // Else keep trying to find a space.
+        // Wrap very long names even though we can't find a space.
+        if (!LastSpace)
+          LastSpace = i;
+        OutStr.insert(LastSpace, "\\l...");
+        ColNum = i - LastSpace;
+        LastSpace = 0;
+        i += 3; // The loop will advance 'i' again.
       }
       else
         ++ColNum;
diff --git a/include/llvm/Analysis/CGSCCPassManager.h b/include/llvm/Analysis/CGSCCPassManager.h
index 09101ae6d0d1..0d4fe932481b 100644
--- a/include/llvm/Analysis/CGSCCPassManager.h
+++ b/include/llvm/Analysis/CGSCCPassManager.h
@@ -18,138 +18,28 @@
 ///
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_ANALYSIS_CGSCC_PASS_MANAGER_H
-#define LLVM_ANALYSIS_CGSCC_PASS_MANAGER_H
+#ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H
+#define LLVM_ANALYSIS_CGSCCPASSMANAGER_H
 
-#include "llvm/IR/PassManager.h"
 #include "llvm/Analysis/LazyCallGraph.h"
+#include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
-class CGSCCAnalysisManager;
-
-class CGSCCPassManager {
-public:
-  // We have to explicitly define all the special member functions because MSVC
-  // refuses to generate them.
-  CGSCCPassManager() {}
-  CGSCCPassManager(CGSCCPassManager &&Arg) : Passes(std::move(Arg.Passes)) {}
-  CGSCCPassManager &operator=(CGSCCPassManager &&RHS) {
-    Passes = std::move(RHS.Passes);
-    return *this;
-  }
-
-  /// \brief Run all of the CGSCC passes in this pass manager over a SCC.
-  PreservedAnalyses run(LazyCallGraph::SCC *C,
-                        CGSCCAnalysisManager *AM = nullptr);
-
-  template <typename CGSCCPassT> void addPass(CGSCCPassT Pass) {
-    Passes.emplace_back(new CGSCCPassModel<CGSCCPassT>(std::move(Pass)));
-  }
-
-  static StringRef name() { return "CGSCCPassManager"; }
-
-private:
-  // Pull in the concept type and model template specialized for SCCs.
-  typedef detail::PassConcept<LazyCallGraph::SCC *, CGSCCAnalysisManager>
-  CGSCCPassConcept;
-  template <typename PassT>
-  struct CGSCCPassModel
-      : detail::PassModel<LazyCallGraph::SCC *, CGSCCAnalysisManager, PassT> {
-    CGSCCPassModel(PassT Pass)
-        : detail::PassModel<LazyCallGraph::SCC *, CGSCCAnalysisManager, PassT>(
-              std::move(Pass)) {}
-  };
-
-  CGSCCPassManager(const CGSCCPassManager &) LLVM_DELETED_FUNCTION;
-  CGSCCPassManager &operator=(const CGSCCPassManager &) LLVM_DELETED_FUNCTION;
-
-  std::vector<std::unique_ptr<CGSCCPassConcept>> Passes;
-};
-
-/// \brief A function analysis manager to coordinate and cache analyses run over
-/// a module.
-class CGSCCAnalysisManager : public detail::AnalysisManagerBase<
-                                 CGSCCAnalysisManager, LazyCallGraph::SCC *> {
-  friend class detail::AnalysisManagerBase<CGSCCAnalysisManager,
-                                           LazyCallGraph::SCC *>;
-  typedef detail::AnalysisManagerBase<CGSCCAnalysisManager,
-                                      LazyCallGraph::SCC *> BaseT;
-  typedef BaseT::ResultConceptT ResultConceptT;
-  typedef BaseT::PassConceptT PassConceptT;
-
-public:
-  // Most public APIs are inherited from the CRTP base class.
-
-  // We have to explicitly define all the special member functions because MSVC
-  // refuses to generate them.
-  CGSCCAnalysisManager() {}
-  CGSCCAnalysisManager(CGSCCAnalysisManager &&Arg)
-      : BaseT(std::move(static_cast<BaseT &>(Arg))),
-        CGSCCAnalysisResults(std::move(Arg.CGSCCAnalysisResults)) {}
-  CGSCCAnalysisManager &operator=(CGSCCAnalysisManager &&RHS) {
-    BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
-    CGSCCAnalysisResults = std::move(RHS.CGSCCAnalysisResults);
-    return *this;
-  }
-
-  /// \brief Returns true if the analysis manager has an empty results cache.
-  bool empty() const;
-
-  /// \brief Clear the function analysis result cache.
-  ///
-  /// This routine allows cleaning up when the set of functions itself has
-  /// potentially changed, and thus we can't even look up a a result and
-  /// invalidate it directly. Notably, this does *not* call invalidate
-  /// functions as there is nothing to be done for them.
-  void clear();
-
-private:
-  CGSCCAnalysisManager(const CGSCCAnalysisManager &) LLVM_DELETED_FUNCTION;
-  CGSCCAnalysisManager &
-  operator=(const CGSCCAnalysisManager &) LLVM_DELETED_FUNCTION;
-
-  /// \brief Get a function pass result, running the pass if necessary.
-  ResultConceptT &getResultImpl(void *PassID, LazyCallGraph::SCC *C);
-
-  /// \brief Get a cached function pass result or return null.
-  ResultConceptT *getCachedResultImpl(void *PassID,
-                                      LazyCallGraph::SCC *C) const;
-
-  /// \brief Invalidate a function pass result.
-  void invalidateImpl(void *PassID, LazyCallGraph::SCC *C);
-
-  /// \brief Invalidate the results for a function..
-  void invalidateImpl(LazyCallGraph::SCC *C, const PreservedAnalyses &PA);
+/// \brief The CGSCC pass manager.
+///
+/// See the documentation for the PassManager template for details. It runs
+/// a sequency of SCC passes over each SCC that the manager is run over. This
+/// typedef serves as a convenient way to refer to this construct.
+typedef PassManager<LazyCallGraph::SCC> CGSCCPassManager;
 
-  /// \brief List of function analysis pass IDs and associated concept pointers.
-  ///
-  /// Requires iterators to be valid across appending new entries and arbitrary
-  /// erases. Provides both the pass ID and concept pointer such that it is
-  /// half of a bijection and provides storage for the actual result concept.
-  typedef std::list<
-      std::pair<void *, std::unique_ptr<detail::AnalysisResultConcept<
-                            LazyCallGraph::SCC *>>>> CGSCCAnalysisResultListT;
-
-  /// \brief Map type from function pointer to our custom list type.
-  typedef DenseMap<LazyCallGraph::SCC *, CGSCCAnalysisResultListT>
-  CGSCCAnalysisResultListMapT;
-
-  /// \brief Map from function to a list of function analysis results.
-  ///
-  /// Provides linear time removal of all analysis results for a function and
-  /// the ultimate storage for a particular cached analysis result.
-  CGSCCAnalysisResultListMapT CGSCCAnalysisResultLists;
-
-  /// \brief Map type from a pair of analysis ID and function pointer to an
-  /// iterator into a particular result list.
-  typedef DenseMap<std::pair<void *, LazyCallGraph::SCC *>,
-                   CGSCCAnalysisResultListT::iterator> CGSCCAnalysisResultMapT;
-
-  /// \brief Map from an analysis ID and function to a particular cached
-  /// analysis result.
-  CGSCCAnalysisResultMapT CGSCCAnalysisResults;
-};
+/// \brief The CGSCC analysis manager.
+///
+/// See the documentation for the AnalysisManager template for detail
+/// documentation. This typedef serves as a convenient way to refer to this
+/// construct in the adaptors and proxies used to integrate this into the larger
+/// pass manager infrastructure.
+typedef AnalysisManager<LazyCallGraph::SCC> CGSCCAnalysisManager;
 
 /// \brief A module analysis which acts as a proxy for a CGSCC analysis
 /// manager.
@@ -187,7 +77,7 @@ public:
     /// Regardless of whether this analysis is marked as preserved, all of the
     /// analyses in the \c CGSCCAnalysisManager are potentially invalidated
     /// based on the set of preserved analyses.
-    bool invalidate(Module *M, const PreservedAnalyses &PA);
+    bool invalidate(Module &M, const PreservedAnalyses &PA);
 
   private:
     CGSCCAnalysisManager *CGAM;
@@ -195,12 +85,13 @@ public:
 
   static void *ID() { return (void *)&PassID; }
 
+  static StringRef name() { return "CGSCCAnalysisManagerModuleProxy"; }
+
   explicit CGSCCAnalysisManagerModuleProxy(CGSCCAnalysisManager &CGAM)
       : CGAM(&CGAM) {}
   // We have to explicitly define all the special member functions because MSVC
   // refuses to generate them.
-  CGSCCAnalysisManagerModuleProxy(
-      const CGSCCAnalysisManagerModuleProxy &Arg)
+  CGSCCAnalysisManagerModuleProxy(const CGSCCAnalysisManagerModuleProxy &Arg)
       : CGAM(Arg.CGAM) {}
   CGSCCAnalysisManagerModuleProxy(CGSCCAnalysisManagerModuleProxy &&Arg)
       : CGAM(std::move(Arg.CGAM)) {}
@@ -219,7 +110,7 @@ public:
   /// In debug builds, it will also assert that the analysis manager is empty
   /// as no queries should arrive at the CGSCC analysis manager prior to
   /// this analysis being requested.
-  Result run(Module *M);
+  Result run(Module &M);
 
 private:
   static char PassID;
@@ -257,7 +148,7 @@ public:
     const ModuleAnalysisManager &getManager() const { return *MAM; }
 
     /// \brief Handle invalidation by ignoring it, this pass is immutable.
-    bool invalidate(LazyCallGraph::SCC *) { return false; }
+    bool invalidate(LazyCallGraph::SCC &) { return false; }
 
   private:
     const ModuleAnalysisManager *MAM;
@@ -265,12 +156,13 @@ public:
 
   static void *ID() { return (void *)&PassID; }
 
+  static StringRef name() { return "ModuleAnalysisManagerCGSCCProxy"; }
+
   ModuleAnalysisManagerCGSCCProxy(const ModuleAnalysisManager &MAM)
       : MAM(&MAM) {}
   // We have to explicitly define all the special member functions because MSVC
   // refuses to generate them.
-  ModuleAnalysisManagerCGSCCProxy(
-      const ModuleAnalysisManagerCGSCCProxy &Arg)
+  ModuleAnalysisManagerCGSCCProxy(const ModuleAnalysisManagerCGSCCProxy &Arg)
       : MAM(Arg.MAM) {}
   ModuleAnalysisManagerCGSCCProxy(ModuleAnalysisManagerCGSCCProxy &&Arg)
       : MAM(std::move(Arg.MAM)) {}
@@ -283,7 +175,7 @@ public:
   /// \brief Run the analysis pass and create our proxy result object.
   /// Nothing to see here, it just forwards the \c MAM reference into the
   /// result.
-  Result run(LazyCallGraph::SCC *) { return Result(*MAM); }
+  Result run(LazyCallGraph::SCC &) { return Result(*MAM); }
 
 private:
   static char PassID;
@@ -323,7 +215,7 @@ public:
   }
 
   /// \brief Runs the CGSCC pass across every SCC in the module.
-  PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM) {
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager *AM) {
     assert(AM && "We need analyses to compute the call graph!");
 
     // Setup the CGSCC analysis manager from its proxy.
@@ -335,15 +227,17 @@ public:
 
     PreservedAnalyses PA = PreservedAnalyses::all();
     for (LazyCallGraph::SCC &C : CG.postorder_sccs()) {
-      PreservedAnalyses PassPA = Pass.run(&C, &CGAM);
+      PreservedAnalyses PassPA = Pass.run(C, &CGAM);
 
       // We know that the CGSCC pass couldn't have invalidated any other
       // SCC's analyses (that's the contract of a CGSCC pass), so
-      // directly handle the CGSCC analysis manager's invalidation here.
+      // directly handle the CGSCC analysis manager's invalidation here. We
+      // also update the preserved set of analyses to reflect that invalidated
+      // analyses are now safe to preserve.
       // FIXME: This isn't quite correct. We need to handle the case where the
       // pass updated the CG, particularly some child of the current SCC, and
       // invalidate its analyses.
-      CGAM.invalidate(&C, PassPA);
+      PassPA = CGAM.invalidate(C, std::move(PassPA));
 
       // Then intersect the preserved set so that invalidation of module
       // analyses will eventually occur when the module pass completes.
@@ -409,7 +303,7 @@ public:
     /// Regardless of whether this analysis is marked as preserved, all of the
     /// analyses in the \c FunctionAnalysisManager are potentially invalidated
     /// based on the set of preserved analyses.
-    bool invalidate(LazyCallGraph::SCC *C, const PreservedAnalyses &PA);
+    bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA);
 
   private:
     FunctionAnalysisManager *FAM;
@@ -417,6 +311,8 @@ public:
 
   static void *ID() { return (void *)&PassID; }
 
+  static StringRef name() { return "FunctionAnalysisManagerCGSCCProxy"; }
+
   explicit FunctionAnalysisManagerCGSCCProxy(FunctionAnalysisManager &FAM)
       : FAM(&FAM) {}
   // We have to explicitly define all the special member functions because MSVC
@@ -441,7 +337,7 @@ public:
   /// In debug builds, it will also assert that the analysis manager is empty
   /// as no queries should arrive at the function analysis manager prior to
   /// this analysis being requested.
-  Result run(LazyCallGraph::SCC *C);
+  Result run(LazyCallGraph::SCC &C);
 
 private:
   static char PassID;
@@ -479,7 +375,7 @@ public:
     const CGSCCAnalysisManager &getManager() const { return *CGAM; }
 
     /// \brief Handle invalidation by ignoring it, this pass is immutable.
-    bool invalidate(Function *) { return false; }
+    bool invalidate(Function &) { return false; }
 
   private:
     const CGSCCAnalysisManager *CGAM;
@@ -487,6 +383,8 @@ public:
 
   static void *ID() { return (void *)&PassID; }
 
+  static StringRef name() { return "CGSCCAnalysisManagerFunctionProxy"; }
+
   CGSCCAnalysisManagerFunctionProxy(const CGSCCAnalysisManager &CGAM)
       : CGAM(&CGAM) {}
   // We have to explicitly define all the special member functions because MSVC
@@ -505,7 +403,7 @@ public:
   /// \brief Run the analysis pass and create our proxy result object.
   /// Nothing to see here, it just forwards the \c CGAM reference into the
   /// result.
-  Result run(Function *) { return Result(*CGAM); }
+  Result run(Function &) { return Result(*CGAM); }
 
 private:
   static char PassID;
@@ -531,7 +429,8 @@ public:
       : Pass(Arg.Pass) {}
   CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
       : Pass(std::move(Arg.Pass)) {}
-  friend void swap(CGSCCToFunctionPassAdaptor &LHS, CGSCCToFunctionPassAdaptor &RHS) {
+  friend void swap(CGSCCToFunctionPassAdaptor &LHS,
+                   CGSCCToFunctionPassAdaptor &RHS) {
     using std::swap;
     swap(LHS.Pass, RHS.Pass);
   }
@@ -541,21 +440,23 @@ public:
   }
 
   /// \brief Runs the function pass across every function in the module.
-  PreservedAnalyses run(LazyCallGraph::SCC *C, CGSCCAnalysisManager *AM) {
+  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager *AM) {
     FunctionAnalysisManager *FAM = nullptr;
     if (AM)
       // Setup the function analysis manager from its proxy.
       FAM = &AM->getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager();
 
     PreservedAnalyses PA = PreservedAnalyses::all();
-    for (LazyCallGraph::Node *N : *C) {
-      PreservedAnalyses PassPA = Pass.run(&N->getFunction(), FAM);
+    for (LazyCallGraph::Node *N : C) {
+      PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM);
 
       // We know that the function pass couldn't have invalidated any other
       // function's analyses (that's the contract of a function pass), so
       // directly handle the function analysis manager's invalidation here.
+      // Also, update the preserved analyses to reflect that once invalidated
+      // these can again be preserved.
       if (FAM)
-        FAM->invalidate(&N->getFunction(), PassPA);
+        PassPA = FAM->invalidate(N->getFunction(), std::move(PassPA));
 
       // Then intersect the preserved set so that invalidation of module
       // analyses will eventually occur when the module pass completes.
@@ -585,7 +486,6 @@ CGSCCToFunctionPassAdaptor<FunctionPassT>
 createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) {
   return std::move(CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass)));
 }
-
 }
 
 #endif
diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h
index 9a6a4a76eb73..76d9073799f8 100644
--- a/include/llvm/Analysis/CallGraph.h
+++ b/include/llvm/Analysis/CallGraph.h
@@ -58,7 +58,6 @@
 #include "llvm/IR/Function.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
-#include "llvm/Support/IncludeFile.h"
 #include <map>
 
 namespace llvm {
@@ -418,13 +417,24 @@ template <> struct GraphTraits<CallGraphNode *> {
 
 template <> struct GraphTraits<const CallGraphNode *> {
   typedef const CallGraphNode NodeType;
-  typedef NodeType::const_iterator ChildIteratorType;
+
+  typedef CallGraphNode::CallRecord CGNPairTy;
+  typedef std::pointer_to_unary_function<CGNPairTy, const CallGraphNode *>
+      CGNDerefFun;
 
   static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; }
+
+  typedef mapped_iterator<NodeType::const_iterator, CGNDerefFun>
+      ChildIteratorType;
+
   static inline ChildIteratorType child_begin(NodeType *N) {
-    return N->begin();
+    return map_iterator(N->begin(), CGNDerefFun(CGNDeref));
   }
-  static inline ChildIteratorType child_end(NodeType *N) { return N->end(); }
+  static inline ChildIteratorType child_end(NodeType *N) {
+    return map_iterator(N->end(), CGNDerefFun(CGNDeref));
+  }
+
+  static const CallGraphNode *CGNDeref(CGNPairTy P) { return P.second; }
 };
 
 template <>
@@ -451,17 +461,24 @@ template <>
 struct GraphTraits<const CallGraph *> : public GraphTraits<
                                             const CallGraphNode *> {
   static NodeType *getEntryNode(const CallGraph *CGN) {
-    return CGN->getExternalCallingNode();
+    return CGN->getExternalCallingNode(); // Start at the external node!
   }
+  typedef std::pair<const Function *, const CallGraphNode *> PairTy;
+  typedef std::pointer_to_unary_function<PairTy, const CallGraphNode &>
+      DerefFun;
+
   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
-  typedef CallGraph::const_iterator nodes_iterator;
-  static nodes_iterator nodes_begin(const CallGraph *CG) { return CG->begin(); }
-  static nodes_iterator nodes_end(const CallGraph *CG) { return CG->end(); }
+  typedef mapped_iterator<CallGraph::const_iterator, DerefFun> nodes_iterator;
+  static nodes_iterator nodes_begin(const CallGraph *CG) {
+    return map_iterator(CG->begin(), DerefFun(CGdereference));
+  }
+  static nodes_iterator nodes_end(const CallGraph *CG) {
+    return map_iterator(CG->end(), DerefFun(CGdereference));
+  }
+
+  static const CallGraphNode &CGdereference(PairTy P) { return *P.second; }
 };
 
 } // End llvm namespace
 
-// Make sure that any clients of this file link in CallGraph.cpp
-FORCE_DEFINING_FILE_TO_BE_LINKED(CallGraph)
-
 #endif
diff --git a/include/llvm/Analysis/CodeMetrics.h b/include/llvm/Analysis/CodeMetrics.h
index 04b39c176946..2f5969129e02 100644
--- a/include/llvm/Analysis/CodeMetrics.h
+++ b/include/llvm/Analysis/CodeMetrics.h
@@ -16,10 +16,13 @@
 #define LLVM_ANALYSIS_CODEMETRICS_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/IR/CallSite.h"
 
 namespace llvm {
+class AssumptionCache;
 class BasicBlock;
+class Loop;
 class Function;
 class Instruction;
 class DataLayout;
@@ -85,7 +88,18 @@ struct CodeMetrics {
         NumInlineCandidates(0), NumVectorInsts(0), NumRets(0) {}
 
   /// \brief Add information about a block to the current state.
-  void analyzeBasicBlock(const BasicBlock *BB, const TargetTransformInfo &TTI);
+  void analyzeBasicBlock(const BasicBlock *BB, const TargetTransformInfo &TTI,
+                         SmallPtrSetImpl<const Value*> &EphValues);
+
+  /// \brief Collect a loop's ephemeral values (those used only by an assume
+  /// or similar intrinsics in the loop).
+  static void collectEphemeralValues(const Loop *L, AssumptionCache *AC,
+                                     SmallPtrSetImpl<const Value *> &EphValues);
+
+  /// \brief Collect a functions's ephemeral values (those used only by an
+  /// assume or similar intrinsics in the function).
+  static void collectEphemeralValues(const Function *L, AssumptionCache *AC,
+                                     SmallPtrSetImpl<const Value *> &EphValues);
 };
 
 }
diff --git a/include/llvm/Analysis/DOTGraphTraitsPass.h b/include/llvm/Analysis/DOTGraphTraitsPass.h
index 53c832cbebee..cb74e9f32d3d 100644
--- a/include/llvm/Analysis/DOTGraphTraitsPass.h
+++ b/include/llvm/Analysis/DOTGraphTraitsPass.h
@@ -66,15 +66,15 @@ public:
   bool runOnFunction(Function &F) override {
     GraphT Graph = AnalysisGraphTraitsT::getGraph(&getAnalysis<AnalysisT>());
     std::string Filename = Name + "." + F.getName().str() + ".dot";
-    std::string ErrorInfo;
+    std::error_code EC;
 
     errs() << "Writing '" << Filename << "'...";
 
-    raw_fd_ostream File(Filename.c_str(), ErrorInfo, sys::fs::F_Text);
+    raw_fd_ostream File(Filename, EC, sys::fs::F_Text);
     std::string GraphName = DOTGraphTraits<GraphT>::getGraphName(Graph);
     std::string Title = GraphName + " for '" + F.getName().str() + "' function";
 
-    if (ErrorInfo.empty())
+    if (!EC)
       WriteGraph(File, Graph, IsSimple, Title);
     else
       errs() << "  error opening file for writing!";
@@ -129,14 +129,14 @@ public:
   bool runOnModule(Module &M) override {
     GraphT Graph = AnalysisGraphTraitsT::getGraph(&getAnalysis<AnalysisT>());
     std::string Filename = Name + ".dot";
-    std::string ErrorInfo;
+    std::error_code EC;
 
     errs() << "Writing '" << Filename << "'...";
 
-    raw_fd_ostream File(Filename.c_str(), ErrorInfo, sys::fs::F_Text);
+    raw_fd_ostream File(Filename, EC, sys::fs::F_Text);
     std::string Title = DOTGraphTraits<GraphT>::getGraphName(Graph);
 
-    if (ErrorInfo.empty())
+    if (!EC)
       WriteGraph(File, Graph, IsSimple, Title);
     else
       errs() << "  error opening file for writing!";
diff --git a/include/llvm/Analysis/DependenceAnalysis.h b/include/llvm/Analysis/DependenceAnalysis.h
index 279755e47622..1041e3f0a4a9 100644
--- a/include/llvm/Analysis/DependenceAnalysis.h
+++ b/include/llvm/Analysis/DependenceAnalysis.h
@@ -287,9 +287,9 @@ namespace llvm {
     /// The flag PossiblyLoopIndependent should be set by the caller
     /// if it appears that control flow can reach from Src to Dst
     /// without traversing a loop back edge.
-    Dependence *depends(Instruction *Src,
-                        Instruction *Dst,
-                        bool PossiblyLoopIndependent);
+    std::unique_ptr<Dependence> depends(Instruction *Src,
+                                        Instruction *Dst,
+                                        bool PossiblyLoopIndependent);
 
     /// getSplitIteration - Give a dependence that's splittable at some
     /// particular level, return the iteration that should be used to split
@@ -331,7 +331,7 @@ namespace llvm {
     ///
     /// breaks the dependence and allows us to vectorize/parallelize
     /// both loops.
-    const SCEV *getSplitIteration(const Dependence *Dep, unsigned Level);
+    const SCEV *getSplitIteration(const Dependence &Dep, unsigned Level);
 
   private:
     AliasAnalysis *AA;
@@ -523,6 +523,12 @@ namespace llvm {
     /// in LoopNest.
     bool isLoopInvariant(const SCEV *Expression, const Loop *LoopNest) const;
 
+    /// Makes sure both subscripts (i.e. Pair->Src and Pair->Dst) share the same
+    /// integer type by sign-extending one of them when necessary.
+    /// Sign-extending a subscript is safe because getelementptr assumes the
+    /// array subscripts are signed.
+    void unifySubscriptType(Subscript *Pair);
+
     /// removeMatchingExtensions - Examines a subscript pair.
     /// If the source and destination are identically sign (or zero)
     /// extended, it strips off the extension in an effort to
@@ -911,7 +917,7 @@ namespace llvm {
 
     bool tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV,
                         SmallVectorImpl<Subscript> &Pair,
-                        const SCEV *ElementSize) const;
+                        const SCEV *ElementSize);
 
   public:
     static char ID; // Class identification, replacement for typeinfo
diff --git a/include/llvm/Analysis/DominanceFrontier.h b/include/llvm/Analysis/DominanceFrontier.h
index f42b9cbbfedd..996700efdb60 100644
--- a/include/llvm/Analysis/DominanceFrontier.h
+++ b/include/llvm/Analysis/DominanceFrontier.h
@@ -102,7 +102,9 @@ public:
   void print(raw_ostream &OS) const;
 
   /// dump - Dump the dominance frontier to dbgs().
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   void dump() const;
+#endif
 };
 
 //===-------------------------------------
diff --git a/include/llvm/Analysis/DominanceFrontierImpl.h b/include/llvm/Analysis/DominanceFrontierImpl.h
index 04df2cc35d46..735bfb83671d 100644
--- a/include/llvm/Analysis/DominanceFrontierImpl.h
+++ b/include/llvm/Analysis/DominanceFrontierImpl.h
@@ -15,8 +15,8 @@
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_IMPL_H
-#define LLVM_ANALYSIS_DOMINANCEFRONTIER_IMPL_H
+#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
+#define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
 
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/Debug.h"
@@ -172,9 +172,7 @@ ForwardDominanceFrontierBase<BlockT>::calculate(const DomTreeT &DT,
     DomSetType &S = this->Frontiers[currentBB];
 
     // Visit each block only once.
-    if (visited.count(currentBB) == 0) {
-      visited.insert(currentBB);
-
+    if (visited.insert(currentBB).second) {
       // Loop over CFG successors to calculate DFlocal[currentNode]
       for (auto SI = BlockTraits::child_begin(currentBB),
                 SE = BlockTraits::child_end(currentBB);
diff --git a/include/llvm/Analysis/FindUsedTypes.h b/include/llvm/Analysis/FindUsedTypes.h
deleted file mode 100644
index 574c947f4ebb..000000000000
--- a/include/llvm/Analysis/FindUsedTypes.h
+++ /dev/null
@@ -1,66 +0,0 @@
-//===- llvm/Analysis/FindUsedTypes.h - Find all Types in use ----*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This pass is used to seek out all of the types in use by the program.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_FINDUSEDTYPES_H
-#define LLVM_ANALYSIS_FINDUSEDTYPES_H
-
-#include "llvm/ADT/SetVector.h"
-#include "llvm/Pass.h"
-
-namespace llvm {
-
-class Type;
-class Value;
-
-class FindUsedTypes : public ModulePass {
-  SetVector<Type *> UsedTypes;
-public:
-  static char ID; // Pass identification, replacement for typeid
-  FindUsedTypes() : ModulePass(ID) {
-    initializeFindUsedTypesPass(*PassRegistry::getPassRegistry());
-  }
-
-  /// getTypes - After the pass has been run, return the set containing all of
-  /// the types used in the module.
-  ///
-  const SetVector<Type *> &getTypes() const { return UsedTypes; }
-
-  /// Print the types found in the module.  If the optional Module parameter is
-  /// passed in, then the types are printed symbolically if possible, using the
-  /// symbol table from the module.
-  ///
-  void print(raw_ostream &o, const Module *M) const override;
-
-private:
-  /// IncorporateType - Incorporate one type and all of its subtypes into the
-  /// collection of used types.
-  ///
-  void IncorporateType(Type *Ty);
-
-  /// IncorporateValue - Incorporate all of the types used by this value.
-  ///
-  void IncorporateValue(const Value *V);
-
-public:
-  /// run - This incorporates all types used by the specified module
-  bool runOnModule(Module &M) override;
-
-  /// getAnalysisUsage - We do not modify anything.
-  void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.setPreservesAll();
-  }
-};
-
-} // End llvm namespace
-
-#endif
diff --git a/include/llvm/Analysis/FunctionTargetTransformInfo.h b/include/llvm/Analysis/FunctionTargetTransformInfo.h
new file mode 100644
index 000000000000..fce5a1a92bd9
--- /dev/null
+++ b/include/llvm/Analysis/FunctionTargetTransformInfo.h
@@ -0,0 +1,49 @@
+//===- llvm/Analysis/FunctionTargetTransformInfo.h --------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass wraps a TargetTransformInfo in a FunctionPass so that it can
+// forward along the current Function so that we can make target specific
+// decisions based on the particular subtarget specified for each Function.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_FUNCTIONTARGETTRANSFORMINFO_H
+#define LLVM_ANALYSIS_FUNCTIONTARGETTRANSFORMINFO_H
+
+#include "TargetTransformInfo.h"
+#include "llvm/Pass.h"
+
+namespace llvm {
+class FunctionTargetTransformInfo final : public FunctionPass {
+private:
+  const Function *Fn;
+  const TargetTransformInfo *TTI;
+
+  FunctionTargetTransformInfo(const FunctionTargetTransformInfo &)
+      LLVM_DELETED_FUNCTION;
+  void operator=(const FunctionTargetTransformInfo &) LLVM_DELETED_FUNCTION;
+
+public:
+  static char ID;
+  FunctionTargetTransformInfo();
+
+  // Implementation boilerplate.
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  void releaseMemory() override;
+  bool runOnFunction(Function &F) override;
+
+  // Shimmed functions from TargetTransformInfo.
+  void
+  getUnrollingPreferences(Loop *L,
+                          TargetTransformInfo::UnrollingPreferences &UP) const {
+    TTI->getUnrollingPreferences(Fn, L, UP);
+  }
+};
+}
+#endif
diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h
index 6038872207c3..d1f037021773 100644
--- a/include/llvm/Analysis/IVUsers.h
+++ b/include/llvm/Analysis/IVUsers.h
@@ -174,7 +174,7 @@ public:
   /// dump - This method is used for debugging.
   void dump() const;
 protected:
-  bool AddUsersImpl(Instruction *I, SmallPtrSet<Loop*,16> &SimpleLoopNests);
+  bool AddUsersImpl(Instruction *I, SmallPtrSetImpl<Loop*> &SimpleLoopNests);
 };
 
 Pass *createIVUsersPass();
diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h
index aaed716b6a11..a064cfc897b0 100644
--- a/include/llvm/Analysis/InlineCost.h
+++ b/include/llvm/Analysis/InlineCost.h
@@ -19,6 +19,7 @@
 #include <climits>
 
 namespace llvm {
+class AssumptionCacheTracker;
 class CallSite;
 class DataLayout;
 class Function;
@@ -100,6 +101,7 @@ public:
 /// \brief Cost analyzer used by inliner.
 class InlineCostAnalysis : public CallGraphSCCPass {
   const TargetTransformInfo *TTI;
+  AssumptionCacheTracker *ACT;
 
 public:
   static char ID;
diff --git a/include/llvm/Analysis/InstructionSimplify.h b/include/llvm/Analysis/InstructionSimplify.h
index 2367c0bf77aa..b88e0899f19a 100644
--- a/include/llvm/Analysis/InstructionSimplify.h
+++ b/include/llvm/Analysis/InstructionSimplify.h
@@ -37,6 +37,7 @@
 namespace llvm {
   template<typename T>
   class ArrayRef;
+  class AssumptionCache;
   class DominatorTree;
   class Instruction;
   class DataLayout;
@@ -50,150 +51,193 @@ namespace llvm {
   Value *SimplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
                          const DataLayout *TD = nullptr,
                          const TargetLibraryInfo *TLI = nullptr,
-                         const DominatorTree *DT = nullptr);
+                         const DominatorTree *DT = nullptr,
+                         AssumptionCache *AC = nullptr,
+                         const Instruction *CxtI = nullptr);
 
   /// SimplifySubInst - Given operands for a Sub, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifySubInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
                          const DataLayout *TD = nullptr,
                          const TargetLibraryInfo *TLI = nullptr,
-                         const DominatorTree *DT = nullptr);
+                         const DominatorTree *DT = nullptr,
+                         AssumptionCache *AC = nullptr,
+                         const Instruction *CxtI = nullptr);
 
   /// Given operands for an FAdd, see if we can fold the result.  If not, this
   /// returns null.
   Value *SimplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF,
-                         const DataLayout *TD = nullptr,
-                         const TargetLibraryInfo *TLI = nullptr,
-                         const DominatorTree *DT = nullptr);
+                          const DataLayout *TD = nullptr,
+                          const TargetLibraryInfo *TLI = nullptr,
+                          const DominatorTree *DT = nullptr,
+                          AssumptionCache *AC = nullptr,
+                          const Instruction *CxtI = nullptr);
 
   /// Given operands for an FSub, see if we can fold the result.  If not, this
   /// returns null.
   Value *SimplifyFSubInst(Value *LHS, Value *RHS, FastMathFlags FMF,
-                         const DataLayout *TD = nullptr,
-                         const TargetLibraryInfo *TLI = nullptr,
-                         const DominatorTree *DT = nullptr);
+                          const DataLayout *TD = nullptr,
+                          const TargetLibraryInfo *TLI = nullptr,
+                          const DominatorTree *DT = nullptr,
+                          AssumptionCache *AC = nullptr,
+                          const Instruction *CxtI = nullptr);
 
   /// Given operands for an FMul, see if we can fold the result.  If not, this
   /// returns null.
-  Value *SimplifyFMulInst(Value *LHS, Value *RHS,
-                          FastMathFlags FMF,
+  Value *SimplifyFMulInst(Value *LHS, Value *RHS, FastMathFlags FMF,
                           const DataLayout *TD = nullptr,
                           const TargetLibraryInfo *TLI = nullptr,
-                          const DominatorTree *DT = nullptr);
+                          const DominatorTree *DT = nullptr,
+                          AssumptionCache *AC = nullptr,
+                          const Instruction *CxtI = nullptr);
 
   /// SimplifyMulInst - Given operands for a Mul, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyMulInst(Value *LHS, Value *RHS, const DataLayout *TD = nullptr,
                          const TargetLibraryInfo *TLI = nullptr,
-                         const DominatorTree *DT = nullptr);
+                         const DominatorTree *DT = nullptr,
+                         AssumptionCache *AC = nullptr,
+                         const Instruction *CxtI = nullptr);
 
   /// SimplifySDivInst - Given operands for an SDiv, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifySDivInst(Value *LHS, Value *RHS,
                           const DataLayout *TD = nullptr,
                           const TargetLibraryInfo *TLI = nullptr,
-                          const DominatorTree *DT = nullptr);
+                          const DominatorTree *DT = nullptr,
+                          AssumptionCache *AC = nullptr,
+                          const Instruction *CxtI = nullptr);
 
   /// SimplifyUDivInst - Given operands for a UDiv, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyUDivInst(Value *LHS, Value *RHS,
                           const DataLayout *TD = nullptr,
                           const TargetLibraryInfo *TLI = nullptr,
-                          const DominatorTree *DT = nullptr);
+                          const DominatorTree *DT = nullptr,
+                          AssumptionCache *AC = nullptr,
+                          const Instruction *CxtI = nullptr);
 
   /// SimplifyFDivInst - Given operands for an FDiv, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyFDivInst(Value *LHS, Value *RHS,
                           const DataLayout *TD = nullptr,
                           const TargetLibraryInfo *TLI = nullptr,
-                          const DominatorTree *DT = nullptr);
+                          const DominatorTree *DT = nullptr,
+                          AssumptionCache *AC = nullptr,
+                          const Instruction *CxtI = nullptr);
 
   /// SimplifySRemInst - Given operands for an SRem, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifySRemInst(Value *LHS, Value *RHS,
                           const DataLayout *TD = nullptr,
                           const TargetLibraryInfo *TLI = nullptr,
-                          const DominatorTree *DT = nullptr);
+                          const DominatorTree *DT = nullptr,
+                          AssumptionCache *AC = nullptr,
+                          const Instruction *CxtI = nullptr);
 
   /// SimplifyURemInst - Given operands for a URem, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyURemInst(Value *LHS, Value *RHS,
                           const DataLayout *TD = nullptr,
                           const TargetLibraryInfo *TLI = nullptr,
-                          const DominatorTree *DT = nullptr);
+                          const DominatorTree *DT = nullptr,
+                          AssumptionCache *AC = nullptr,
+                          const Instruction *CxtI = nullptr);
 
   /// SimplifyFRemInst - Given operands for an FRem, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyFRemInst(Value *LHS, Value *RHS,
                           const DataLayout *TD = nullptr,
                           const TargetLibraryInfo *TLI = nullptr,
-                          const DominatorTree *DT = nullptr);
+                          const DominatorTree *DT = nullptr,
+                          AssumptionCache *AC = nullptr,
+                          const Instruction *CxtI = nullptr);
 
   /// SimplifyShlInst - Given operands for a Shl, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
                          const DataLayout *TD = nullptr,
                          const TargetLibraryInfo *TLI = nullptr,
-                         const DominatorTree *DT = nullptr);
+                         const DominatorTree *DT = nullptr,
+                         AssumptionCache *AC = nullptr,
+                         const Instruction *CxtI = nullptr);
 
   /// SimplifyLShrInst - Given operands for a LShr, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
                           const DataLayout *TD = nullptr,
                           const TargetLibraryInfo *TLI = nullptr,
-                          const DominatorTree *DT = nullptr);
+                          const DominatorTree *DT = nullptr,
+                          AssumptionCache *AC = nullptr,
+                          const Instruction *CxtI = nullptr);
 
   /// SimplifyAShrInst - Given operands for a AShr, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
                           const DataLayout *TD = nullptr,
                           const TargetLibraryInfo *TLI = nullptr,
-                          const DominatorTree *DT = nullptr);
+                          const DominatorTree *DT = nullptr,
+                          AssumptionCache *AC = nullptr,
+                          const Instruction *CxtI = nullptr);
 
   /// SimplifyAndInst - Given operands for an And, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyAndInst(Value *LHS, Value *RHS, const DataLayout *TD = nullptr,
                          const TargetLibraryInfo *TLI = nullptr,
-                         const DominatorTree *DT = nullptr);
+                         const DominatorTree *DT = nullptr,
+                         AssumptionCache *AC = nullptr,
+                         const Instruction *CxtI = nullptr);
 
   /// SimplifyOrInst - Given operands for an Or, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyOrInst(Value *LHS, Value *RHS, const DataLayout *TD = nullptr,
                         const TargetLibraryInfo *TLI = nullptr,
-                        const DominatorTree *DT = nullptr);
+                        const DominatorTree *DT = nullptr,
+                        AssumptionCache *AC = nullptr,
+                        const Instruction *CxtI = nullptr);
 
   /// SimplifyXorInst - Given operands for a Xor, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyXorInst(Value *LHS, Value *RHS, const DataLayout *TD = nullptr,
                          const TargetLibraryInfo *TLI = nullptr,
-                         const DominatorTree *DT = nullptr);
+                         const DominatorTree *DT = nullptr,
+                         AssumptionCache *AC = nullptr,
+                         const Instruction *CxtI = nullptr);
 
   /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
                           const DataLayout *TD = nullptr,
                           const TargetLibraryInfo *TLI = nullptr,
-                          const DominatorTree *DT = nullptr);
+                          const DominatorTree *DT = nullptr,
+                          AssumptionCache *AC = nullptr,
+                          Instruction *CxtI = nullptr);
 
   /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
                           const DataLayout *TD = nullptr,
                           const TargetLibraryInfo *TLI = nullptr,
-                          const DominatorTree *DT = nullptr);
+                          const DominatorTree *DT = nullptr,
+                          AssumptionCache *AC = nullptr,
+                          const Instruction *CxtI = nullptr);
 
   /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
   /// the result.  If not, this returns null.
   Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
                             const DataLayout *TD = nullptr,
                             const TargetLibraryInfo *TLI = nullptr,
-                            const DominatorTree *DT = nullptr);
+                            const DominatorTree *DT = nullptr,
+                            AssumptionCache *AC = nullptr,
+                            const Instruction *CxtI = nullptr);
 
   /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const DataLayout *TD = nullptr,
                          const TargetLibraryInfo *TLI = nullptr,
-                         const DominatorTree *DT = nullptr);
+                         const DominatorTree *DT = nullptr,
+                         AssumptionCache *AC = nullptr,
+                         const Instruction *CxtI = nullptr);
 
   /// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we
   /// can fold the result.  If not, this returns null.
@@ -201,13 +245,17 @@ namespace llvm {
                                  ArrayRef<unsigned> Idxs,
                                  const DataLayout *TD = nullptr,
                                  const TargetLibraryInfo *TLI = nullptr,
-                                 const DominatorTree *DT = nullptr);
+                                 const DominatorTree *DT = nullptr,
+                                 AssumptionCache *AC = nullptr,
+                                 const Instruction *CxtI = nullptr);
 
   /// SimplifyTruncInst - Given operands for an TruncInst, see if we can fold
   /// the result.  If not, this returns null.
   Value *SimplifyTruncInst(Value *Op, Type *Ty, const DataLayout *TD = nullptr,
                            const TargetLibraryInfo *TLI = nullptr,
-                           const DominatorTree *DT = nullptr);
+                           const DominatorTree *DT = nullptr,
+                           AssumptionCache *AC = nullptr,
+                           const Instruction *CxtI = nullptr);
 
   //=== Helper functions for higher up the class hierarchy.
 
@@ -217,14 +265,18 @@ namespace llvm {
   Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
                          const DataLayout *TD = nullptr,
                          const TargetLibraryInfo *TLI = nullptr,
-                         const DominatorTree *DT = nullptr);
+                         const DominatorTree *DT = nullptr,
+                         AssumptionCache *AC = nullptr,
+                         const Instruction *CxtI = nullptr);
 
   /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
                        const DataLayout *TD = nullptr,
                        const TargetLibraryInfo *TLI = nullptr,
-                       const DominatorTree *DT = nullptr);
+                       const DominatorTree *DT = nullptr,
+                       AssumptionCache *AC = nullptr,
+                       const Instruction *CxtI = nullptr);
 
   /// \brief Given a function and iterators over arguments, see if we can fold
   /// the result.
@@ -233,7 +285,9 @@ namespace llvm {
   Value *SimplifyCall(Value *V, User::op_iterator ArgBegin,
                       User::op_iterator ArgEnd, const DataLayout *TD = nullptr,
                       const TargetLibraryInfo *TLI = nullptr,
-                      const DominatorTree *DT = nullptr);
+                      const DominatorTree *DT = nullptr,
+                      AssumptionCache *AC = nullptr,
+                      const Instruction *CxtI = nullptr);
 
   /// \brief Given a function and set of arguments, see if we can fold the
   /// result.
@@ -242,14 +296,16 @@ namespace llvm {
   Value *SimplifyCall(Value *V, ArrayRef<Value *> Args,
                       const DataLayout *TD = nullptr,
                       const TargetLibraryInfo *TLI = nullptr,
-                      const DominatorTree *DT = nullptr);
+                      const DominatorTree *DT = nullptr,
+                      AssumptionCache *AC = nullptr,
+                      const Instruction *CxtI = nullptr);
 
   /// SimplifyInstruction - See if we can compute a simplified version of this
   /// instruction.  If not, this returns null.
   Value *SimplifyInstruction(Instruction *I, const DataLayout *TD = nullptr,
                              const TargetLibraryInfo *TLI = nullptr,
-                             const DominatorTree *DT = nullptr);
-
+                             const DominatorTree *DT = nullptr,
+                             AssumptionCache *AC = nullptr);
 
   /// \brief Replace all uses of 'I' with 'SimpleV' and simplify the uses
   /// recursively.
@@ -262,7 +318,8 @@ namespace llvm {
   bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV,
                                      const DataLayout *TD = nullptr,
                                      const TargetLibraryInfo *TLI = nullptr,
-                                     const DominatorTree *DT = nullptr);
+                                     const DominatorTree *DT = nullptr,
+                                     AssumptionCache *AC = nullptr);
 
   /// \brief Recursively attempt to simplify an instruction.
   ///
@@ -273,7 +330,8 @@ namespace llvm {
   bool recursivelySimplifyInstruction(Instruction *I,
                                       const DataLayout *TD = nullptr,
                                       const TargetLibraryInfo *TLI = nullptr,
-                                      const DominatorTree *DT = nullptr);
+                                      const DominatorTree *DT = nullptr,
+                                      AssumptionCache *AC = nullptr);
 } // end namespace llvm
 
 #endif
diff --git a/include/llvm/Analysis/IntervalIterator.h b/include/llvm/Analysis/IntervalIterator.h
index 73aff76efe83..3b51d44099fa 100644
--- a/include/llvm/Analysis/IntervalIterator.h
+++ b/include/llvm/Analysis/IntervalIterator.h
@@ -165,10 +165,10 @@ private:
   //
   bool ProcessInterval(NodeTy *Node) {
     BasicBlock *Header = getNodeHeader(Node);
-    if (Visited.count(Header)) return false;
+    if (!Visited.insert(Header).second)
+      return false;
 
     Interval *Int = new Interval(Header);
-    Visited.insert(Header);   // The header has now been visited!
 
     // Check all of our successors to see if they are in the interval...
     for (typename GT::ChildIteratorType I = GT::child_begin(Node),
diff --git a/include/llvm/Analysis/JumpInstrTableInfo.h b/include/llvm/Analysis/JumpInstrTableInfo.h
index 54760aa02466..591e794a3901 100644
--- a/include/llvm/Analysis/JumpInstrTableInfo.h
+++ b/include/llvm/Analysis/JumpInstrTableInfo.h
@@ -16,7 +16,6 @@
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Pass.h"
-
 #include <vector>
 
 namespace llvm {
@@ -37,7 +36,9 @@ class JumpInstrTableInfo : public ImmutablePass {
 public:
   static char ID;
 
-  JumpInstrTableInfo();
+  /// The default byte alignment for jump tables is 16, which is large but
+  /// usually safe.
+  JumpInstrTableInfo(uint64_t ByteAlign = 16);
   virtual ~JumpInstrTableInfo();
   const char *getPassName() const override {
     return "Jump-Instruction Table Info";
@@ -52,9 +53,19 @@ public:
   /// Gets the tables.
   const JumpTables &getTables() const { return Tables; }
 
+  /// Gets the alignment in bytes of a jumptable entry.
+  uint64_t entryByteAlignment() const { return ByteAlignment; }
 private:
   JumpTables Tables;
+
+  /// A power-of-two alignment of a jumptable entry.
+  uint64_t ByteAlignment;
 };
+
+/// Creates a JumpInstrTableInfo pass with the given bound on entry size. This
+/// bound specifies the maximum number of bytes needed to represent an
+/// unconditional jump or a trap instruction in the back end currently in use.
+ModulePass *createJumpInstrTableInfoPass(unsigned Bound);
 }
 
 #endif /* LLVM_ANALYSIS_JUMPINSTRTABLEINFO_H */
diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h
index 70a4df51c1ed..b0b9068de34b 100644
--- a/include/llvm/Analysis/LazyCallGraph.h
+++ b/include/llvm/Analysis/LazyCallGraph.h
@@ -32,8 +32,8 @@
 ///
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_ANALYSIS_LAZY_CALL_GRAPH
-#define LLVM_ANALYSIS_LAZY_CALL_GRAPH
+#ifndef LLVM_ANALYSIS_LAZYCALLGRAPH_H
+#define LLVM_ANALYSIS_LAZYCALLGRAPH_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PointerUnion.h"
@@ -46,11 +46,11 @@
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
 #include "llvm/Support/Allocator.h"
 #include <iterator>
 
 namespace llvm {
-class ModuleAnalysisManager;
 class PreservedAnalyses;
 class raw_ostream;
 
@@ -252,6 +252,12 @@ public:
     /// \brief Test if this SCC is a descendant of \a C.
     bool isDescendantOf(const SCC &C) const;
 
+    /// \brief Short name useful for debugging or logging.
+    ///
+    /// We use the name of the first function in the SCC to name the SCC for
+    /// the purposes of debugging and logging.
+    StringRef getName() const { return (*begin())->getFunction().getName(); }
+
     ///@{
     /// \name Mutation API
     ///
@@ -537,11 +543,13 @@ public:
 
   static void *ID() { return (void *)&PassID; }
 
-  /// \brief Compute the \c LazyCallGraph for a the module \c M.
+  static StringRef name() { return "Lazy CallGraph Analysis"; }
+
+  /// \brief Compute the \c LazyCallGraph for the module \c M.
   ///
   /// This just builds the set of entry points to the call graph. The rest is
   /// built lazily as it is walked.
-  LazyCallGraph run(Module *M) { return LazyCallGraph(*M); }
+  LazyCallGraph run(Module &M) { return LazyCallGraph(M); }
 
 private:
   static char PassID;
@@ -556,7 +564,7 @@ class LazyCallGraphPrinterPass {
 public:
   explicit LazyCallGraphPrinterPass(raw_ostream &OS);
 
-  PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM);
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager *AM);
 
   static StringRef name() { return "LazyCallGraphPrinterPass"; }
 };
diff --git a/include/llvm/Analysis/LazyValueInfo.h b/include/llvm/Analysis/LazyValueInfo.h
index 2fe7386e7302..9a67d52c3696 100644
--- a/include/llvm/Analysis/LazyValueInfo.h
+++ b/include/llvm/Analysis/LazyValueInfo.h
@@ -18,16 +18,20 @@
 #include "llvm/Pass.h"
 
 namespace llvm {
+  class AssumptionCache;
   class Constant;
   class DataLayout;
+  class DominatorTree;
+  class Instruction;
   class TargetLibraryInfo;
   class Value;
   
-/// LazyValueInfo - This pass computes, caches, and vends lazy value constraint
-/// information.
+/// This pass computes, caches, and vends lazy value constraint information.
 class LazyValueInfo : public FunctionPass {
+  AssumptionCache *AC;
   const DataLayout *DL;
   class TargetLibraryInfo *TLI;
+  DominatorTree *DT;
   void *PImpl;
   LazyValueInfo(const LazyValueInfo&) LLVM_DELETED_FUNCTION;
   void operator=(const LazyValueInfo&) LLVM_DELETED_FUNCTION;
@@ -38,7 +42,7 @@ public:
   }
   ~LazyValueInfo() { assert(!PImpl && "releaseMemory not called"); }
 
-  /// Tristate - This is used to return true/false/dunno results.
+  /// This is used to return true/false/dunno results.
   enum Tristate {
     Unknown = -1, False = 0, True = 1
   };
@@ -46,26 +50,33 @@ public:
   
   // Public query interface.
   
-  /// getPredicateOnEdge - Determine whether the specified value comparison
-  /// with a constant is known to be true or false on the specified CFG edge.
+  /// Determine whether the specified value comparison with a constant is known
+  /// to be true or false on the specified CFG edge.
   /// Pred is a CmpInst predicate.
   Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
-                              BasicBlock *FromBB, BasicBlock *ToBB);
+                              BasicBlock *FromBB, BasicBlock *ToBB,
+                              Instruction *CxtI = nullptr);
   
-  
-  /// getConstant - Determine whether the specified value is known to be a
+  /// Determine whether the specified value comparison with a constant is known
+  /// to be true or false at the specified instruction
+  /// (from an assume intrinsic). Pred is a CmpInst predicate.
+  Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C,
+                          Instruction *CxtI);
+ 
+  /// Determine whether the specified value is known to be a
   /// constant at the end of the specified block.  Return null if not.
-  Constant *getConstant(Value *V, BasicBlock *BB);
+  Constant *getConstant(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr);
 
-  /// getConstantOnEdge - Determine whether the specified value is known to be a
+  /// Determine whether the specified value is known to be a
   /// constant on the specified edge.  Return null if not.
-  Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB);
+  Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
+                              Instruction *CxtI = nullptr);
   
-  /// threadEdge - Inform the analysis cache that we have threaded an edge from
+  /// Inform the analysis cache that we have threaded an edge from
   /// PredBB to OldSucc to be from PredBB to NewSucc instead.
   void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc);
   
-  /// eraseBlock - Inform the analysis cache that we have erased a block.
+  /// Inform the analysis cache that we have erased a block.
   void eraseBlock(BasicBlock *BB);
   
   // Implementation boilerplate.
diff --git a/include/llvm/Analysis/Loads.h b/include/llvm/Analysis/Loads.h
index 25c59288f34b..0fe34539f8f7 100644
--- a/include/llvm/Analysis/Loads.h
+++ b/include/llvm/Analysis/Loads.h
@@ -44,14 +44,14 @@ bool isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom,
 /// If it is set to 0, it will scan the whole block. You can also optionally
 /// specify an alias analysis implementation, which makes this more precise.
 ///
-/// If TBAATag is non-null and a load or store is found, the TBAA tag from the
-/// load or store is recorded there.  If there is no TBAA tag or if no access
+/// If AATags is non-null and a load or store is found, the AA tags from the
+/// load or store are recorded there.  If there are no AA tags or if no access
 /// is found, it is left unmodified.
 Value *FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB,
                                 BasicBlock::iterator &ScanFrom,
                                 unsigned MaxInstsToScan = 6,
                                 AliasAnalysis *AA = nullptr,
-                                MDNode **TBAATag = nullptr);
+                                AAMDNodes *AATags = nullptr);
 
 }
 
diff --git a/include/llvm/Analysis/LoopPass.h b/include/llvm/Analysis/LoopPass.h
index 726e28636ac6..8650000fcfb6 100644
--- a/include/llvm/Analysis/LoopPass.h
+++ b/include/llvm/Analysis/LoopPass.h
@@ -82,6 +82,11 @@ public:
   /// deleteAnalysisValue - Delete analysis info associated with value V.
   virtual void deleteAnalysisValue(Value *V, Loop *L) {}
 
+  /// Delete analysis info associated with Loop L.
+  /// Called to notify a Pass that a loop has been deleted and any
+  /// associated analysis values can be deleted.
+  virtual void deleteAnalysisLoop(Loop *L) {}
+
 protected:
   /// skipOptnoneFunction - Containing function has Attribute::OptimizeNone
   /// and most transformation passes should skip it.
@@ -152,6 +157,10 @@ public:
   /// that implement simple analysis interface.
   void deleteSimpleAnalysisValue(Value *V, Loop *L);
 
+  /// Invoke deleteAnalysisLoop hook for all passes that implement simple
+  /// analysis interface.
+  void deleteSimpleAnalysisLoop(Loop *L);
+
 private:
   std::deque<Loop *> LQ;
   bool skipThisLoop;
diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
index 1c4441bea670..67fd70a4561f 100644
--- a/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -28,6 +28,7 @@ namespace llvm {
   class Instruction;
   class CallSite;
   class AliasAnalysis;
+  class AssumptionCache;
   class DataLayout;
   class MemoryDependenceAnalysis;
   class PredIteratorCache;
@@ -281,12 +282,12 @@ namespace llvm {
       /// Size - The maximum size of the dereferences of the
       /// pointer. May be UnknownSize if the sizes are unknown.
       uint64_t Size;
-      /// TBAATag - The TBAA tag associated with dereferences of the
-      /// pointer. May be null if there are no tags or conflicting tags.
-      const MDNode *TBAATag;
+      /// AATags - The AA tags associated with dereferences of the
+      /// pointer. The members may be null if there are no tags or
+      /// conflicting tags.
+      AAMDNodes AATags;
 
-      NonLocalPointerInfo()
-        : Size(AliasAnalysis::UnknownSize), TBAATag(nullptr) {}
+      NonLocalPointerInfo() : Size(AliasAnalysis::UnknownSize) {}
     };
 
     /// CachedNonLocalPointerInfo - This map stores the cached results of doing
@@ -325,6 +326,7 @@ namespace llvm {
     AliasAnalysis *AA;
     const DataLayout *DL;
     DominatorTree *DT;
+    AssumptionCache *AC;
     std::unique_ptr<PredIteratorCache> PredCache;
 
   public:
@@ -364,12 +366,16 @@ namespace llvm {
 
 
     /// getNonLocalPointerDependency - Perform a full dependency query for an
-    /// access to the specified (non-volatile) memory location, returning the
-    /// set of instructions that either define or clobber the value.
+    /// access to the QueryInst's specified memory location, returning the set
+    /// of instructions that either define or clobber the value.
     ///
-    /// This method assumes the pointer has a "NonLocal" dependency within BB.
-    void getNonLocalPointerDependency(const AliasAnalysis::Location &Loc,
-                                      bool isLoad, BasicBlock *BB,
+    /// Warning: For a volatile query instruction, the dependencies will be
+    /// accurate, and thus usable for reordering, but it is never legal to
+    /// remove the query instruction.  
+    ///
+    /// This method assumes the pointer has a "NonLocal" dependency within
+    /// QueryInst's parent basic block.
+    void getNonLocalPointerDependency(Instruction *QueryInst,
                                     SmallVectorImpl<NonLocalDepResult> &Result);
 
     /// removeInstruction - Remove an instruction from the dependence analysis,
diff --git a/include/llvm/Analysis/PHITransAddr.h b/include/llvm/Analysis/PHITransAddr.h
index 69f59071f94f..38730d8ea4f3 100644
--- a/include/llvm/Analysis/PHITransAddr.h
+++ b/include/llvm/Analysis/PHITransAddr.h
@@ -18,6 +18,7 @@
 #include "llvm/IR/Instruction.h"
 
 namespace llvm {
+  class AssumptionCache;
   class DominatorTree;
   class DataLayout;
   class TargetLibraryInfo;
@@ -41,12 +42,15 @@ class PHITransAddr {
 
   /// TLI - The target library info if known, otherwise null.
   const TargetLibraryInfo *TLI;
-  
+
+  /// A cache of @llvm.assume calls used by SimplifyInstruction.
+  AssumptionCache *AC;
+
   /// InstInputs - The inputs for our symbolic address.
   SmallVector<Instruction*, 4> InstInputs;
 public:
-  PHITransAddr(Value *addr, const DataLayout *DL)
-      : Addr(addr), DL(DL), TLI(nullptr) {
+  PHITransAddr(Value *addr, const DataLayout *DL, AssumptionCache *AC)
+      : Addr(addr), DL(DL), TLI(nullptr), AC(AC) {
     // If the address is an instruction, the whole thing is considered an input.
     if (Instruction *I = dyn_cast<Instruction>(Addr))
       InstInputs.push_back(I);
diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h
index fd65ae5ca5b2..10a56059ae10 100644
--- a/include/llvm/Analysis/Passes.h
+++ b/include/llvm/Analysis/Passes.h
@@ -66,6 +66,13 @@ namespace llvm {
 
   //===--------------------------------------------------------------------===//
   //
+  // createCFLAliasAnalysisPass - This pass implements a set-based approach to
+  // alias analysis.
+  //
+  ImmutablePass *createCFLAliasAnalysisPass();
+
+  //===--------------------------------------------------------------------===//
+  //
   /// createLibCallAliasAnalysisPass - Create an alias analysis pass that knows
   /// about the semantics of a set of libcalls specified by LCI.  The newly
   /// constructed pass takes ownership of the pointer that is provided.
@@ -88,11 +95,20 @@ namespace llvm {
 
   //===--------------------------------------------------------------------===//
   //
+  // createScopedNoAliasAAPass - This pass implements metadata-based
+  // scoped noalias analysis.
+  //
+  ImmutablePass *createScopedNoAliasAAPass();
+
+  //===--------------------------------------------------------------------===//
+  //
   // createObjCARCAliasAnalysisPass - This pass implements ObjC-ARC-based
   // alias analysis.
   //
   ImmutablePass *createObjCARCAliasAnalysisPass();
 
+  FunctionPass *createPAEvalPass();
+
   //===--------------------------------------------------------------------===//
   //
   /// createLazyValueInfoPass - This creates an instance of the LazyValueInfo
diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h
index d330755a0871..72cd35754c8a 100644
--- a/include/llvm/Analysis/PostDominators.h
+++ b/include/llvm/Analysis/PostDominators.h
@@ -19,7 +19,7 @@
 namespace llvm {
 
 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
-/// compute the a post-dominator tree.
+/// compute the post-dominator tree.
 ///
 struct PostDominatorTree : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h
index 49c88fd5caeb..6ff7f97d01f5 100644
--- a/include/llvm/Analysis/RegionInfo.h
+++ b/include/llvm/Analysis/RegionInfo.h
@@ -424,8 +424,10 @@ public:
   void print(raw_ostream &OS, bool printTree = true, unsigned level = 0,
              PrintStyle Style = PrintNone) const;
 
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// @brief Print the region to stderr.
   void dump() const;
+#endif
 
   /// @brief Check if the region contains a BasicBlock.
   ///
@@ -732,7 +734,9 @@ public:
   static typename RegionT::PrintStyle printStyle;
 
   void print(raw_ostream &OS) const;
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   void dump() const;
+#endif
 
   void releaseMemory();
 
diff --git a/include/llvm/Analysis/RegionInfoImpl.h b/include/llvm/Analysis/RegionInfoImpl.h
index 4266b84c32c4..b0dc26312aaa 100644
--- a/include/llvm/Analysis/RegionInfoImpl.h
+++ b/include/llvm/Analysis/RegionInfoImpl.h
@@ -12,11 +12,11 @@
 #ifndef LLVM_ANALYSIS_REGIONINFOIMPL_H
 #define LLVM_ANALYSIS_REGIONINFOIMPL_H
 
-#include "llvm/Analysis/RegionInfo.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/Analysis/DominanceFrontier.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/RegionIterator.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
@@ -25,7 +25,7 @@
 #include <iterator>
 #include <set>
 
-using namespace llvm;
+namespace llvm {
 
 #define DEBUG_TYPE "region"
 
@@ -916,4 +916,8 @@ void RegionInfoBase<Tr>::calculate(FuncT &F) {
   buildRegionsTree(DT->getNode(BB), TopLevelRegion);
 }
 
+#undef DEBUG_TYPE
+
+} // end namespace llvm
+
 #endif
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index 617e54541ee1..f394e335257f 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -35,6 +35,7 @@
 
 namespace llvm {
   class APInt;
+  class AssumptionCache;
   class Constant;
   class ConstantInt;
   class DominatorTree;
@@ -128,9 +129,11 @@ namespace llvm {
     /// purposes.
     void print(raw_ostream &OS) const;
 
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     /// dump - This method is used for debugging.
     ///
     void dump() const;
+#endif
   };
 
   // Specialize FoldingSetTrait for SCEV to avoid needing to compute
@@ -221,6 +224,9 @@ namespace llvm {
     ///
     Function *F;
 
+    /// The tracker for @llvm.assume intrinsics in this function.
+    AssumptionCache *AC;
+
     /// LI - The loop information for the function we are currently analyzing.
     ///
     LoopInfo *LI;
@@ -257,24 +263,13 @@ namespace llvm {
     /// loop exit's branch condition evaluates to the not-taken path.  This is a
     /// temporary pair of exact and max expressions that are eventually
     /// summarized in ExitNotTakenInfo and BackedgeTakenInfo.
-    ///
-    /// If MustExit is true, then the exit must be taken when the BECount
-    /// reaches Exact (and before surpassing Max). If MustExit is false, then
-    /// BECount may exceed Exact or Max if the loop exits via another branch. In
-    /// either case, the loop may exit early via another branch.
-    ///
-    /// MustExit is true for most cases. However, an exit guarded by an
-    /// (in)equality on a nonunit stride may be skipped.
     struct ExitLimit {
       const SCEV *Exact;
       const SCEV *Max;
-      bool MustExit;
 
-      /*implicit*/ ExitLimit(const SCEV *E)
-        : Exact(E), Max(E), MustExit(true) {}
+      /*implicit*/ ExitLimit(const SCEV *E) : Exact(E), Max(E) {}
 
-      ExitLimit(const SCEV *E, const SCEV *M, bool MustExit)
-        : Exact(E), Max(M), MustExit(MustExit) {}
+      ExitLimit(const SCEV *E, const SCEV *M) : Exact(E), Max(M) {}
 
       /// hasAnyInfo - Test whether this ExitLimit contains any computed
       /// information, or whether it's all SCEVCouldNotCompute values.
@@ -749,6 +744,13 @@ namespace llvm {
     bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
                                      const SCEV *LHS, const SCEV *RHS);
 
+    /// \brief Returns the maximum trip count of the loop if it is a single-exit
+    /// loop and we can compute a small maximum for that loop.
+    ///
+    /// Implemented in terms of the \c getSmallConstantTripCount overload with
+    /// the single exiting block passed to it. See that routine for details.
+    unsigned getSmallConstantTripCount(Loop *L);
+
     /// getSmallConstantTripCount - Returns the maximum trip count of this loop
     /// as a normal unsigned value. Returns 0 if the trip count is unknown or
     /// not constant. This "trip count" assumes that control exits via
@@ -758,6 +760,14 @@ namespace llvm {
     /// the loop exits prematurely via another branch.
     unsigned getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock);
 
+    /// \brief Returns the largest constant divisor of the trip count of the
+    /// loop if it is a single-exit loop and we can compute a small maximum for
+    /// that loop.
+    ///
+    /// Implemented in terms of the \c getSmallConstantTripMultiple overload with
+    /// the single exiting block passed to it. See that routine for details.
+    unsigned getSmallConstantTripMultiple(Loop *L);
+
     /// getSmallConstantTripMultiple - Returns the largest constant divisor of
     /// the trip count of this loop as a normal unsigned value, if
     /// possible. This means that the actual trip count is always a multiple of
diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
index 2f1b1c3841f3..ff82db19b9e7 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -14,8 +14,8 @@
 #ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
 #define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
 
-#include "llvm/ADT/iterator_range.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Support/ErrorHandling.h"
 
@@ -577,7 +577,7 @@ namespace llvm {
     SmallPtrSet<const SCEV *, 8> Visited;
 
     void push(const SCEV *S) {
-      if (Visited.insert(S) && Visitor.follow(S))
+      if (Visited.insert(S).second && Visitor.follow(S))
         Worklist.push_back(S);
     }
   public:
@@ -624,7 +624,7 @@ namespace llvm {
     }
   };
 
-  /// Use SCEVTraversal to visit all nodes in the givien expression tree.
+  /// Use SCEVTraversal to visit all nodes in the given expression tree.
   template<typename SV>
   void visitAll(const SCEV *Root, SV& Visitor) {
     SCEVTraversal<SV> T(Visitor);
diff --git a/include/llvm/Analysis/TargetTransformInfo.h b/include/llvm/Analysis/TargetTransformInfo.h
index f57f3eb009a1..4bd5dd8a221e 100644
--- a/include/llvm/Analysis/TargetTransformInfo.h
+++ b/include/llvm/Analysis/TargetTransformInfo.h
@@ -28,6 +28,7 @@
 
 namespace llvm {
 
+class Function;
 class GlobalValue;
 class Loop;
 class Type;
@@ -183,7 +184,7 @@ public:
   /// should probably move to simpler cost metrics using the above.
   /// Alternatively, we could split the cost interface into distinct code-size
   /// and execution-speed costs. This would allow modelling the core of this
-  /// query more accurately as the a call is a single small instruction, but
+  /// query more accurately as a call is a single small instruction, but
   /// incurs significant execution cost.
   virtual bool isLoweredToCall(const Function *F) const;
 
@@ -227,7 +228,8 @@ public:
   /// \brief Get target-customized preferences for the generic loop unrolling
   /// transformation. The caller will initialize UP with the current
   /// target-independent defaults.
-  virtual void getUnrollingPreferences(Loop *L, UnrollingPreferences &UP) const;
+  virtual void getUnrollingPreferences(const Function *F, Loop *L,
+                                       UnrollingPreferences &UP) const;
 
   /// @}
 
@@ -268,6 +270,13 @@ public:
                                      int64_t BaseOffset, bool HasBaseReg,
                                      int64_t Scale) const;
 
+  /// \brief Return true if the target works with masked instruction
+  /// AVX2 allows masks for consecutive load and store for i32 and i64 elements.
+  /// AVX-512 architecture will also allow masks for non-consecutive memory
+  /// accesses.
+  virtual bool isLegalMaskedStore(Type *DataType, int Consecutive) const;
+  virtual bool isLegalMaskedLoad (Type *DataType, int Consecutive) const;
+
   /// \brief Return the cost of the scaling factor used in the addressing
   /// mode represented by AM for this target, for a load/store
   /// of the specified type.
@@ -335,6 +344,9 @@ public:
     OK_NonUniformConstantValue   // Operand is a non uniform constant value.
   };
 
+  /// \brief Additional properties of an operand's values.
+  enum OperandValueProperties { OP_None = 0, OP_PowerOf2 = 1 };
+
   /// \return The number of scalar or vector registers that the target has.
   /// If 'Vectors' is true, it returns the number of vector registers. If it is
   /// set to false, it returns the number of scalar registers.
@@ -343,15 +355,18 @@ public:
   /// \return The width of the largest scalar or vector register type.
   virtual unsigned getRegisterBitWidth(bool Vector) const;
 
-  /// \return The maximum unroll factor that the vectorizer should try to
+  /// \return The maximum interleave factor that any transform should try to
   /// perform for this target. This number depends on the level of parallelism
   /// and the number of execution units in the CPU.
-  virtual unsigned getMaximumUnrollFactor() const;
+  virtual unsigned getMaxInterleaveFactor() const;
 
   /// \return The expected cost of arithmetic ops, such as mul, xor, fsub, etc.
-  virtual unsigned getArithmeticInstrCost(unsigned Opcode, Type *Ty,
-                                  OperandValueKind Opd1Info = OK_AnyValue,
-                                  OperandValueKind Opd2Info = OK_AnyValue) const;
+  virtual unsigned
+  getArithmeticInstrCost(unsigned Opcode, Type *Ty,
+                         OperandValueKind Opd1Info = OK_AnyValue,
+                         OperandValueKind Opd2Info = OK_AnyValue,
+                         OperandValueProperties Opd1PropInfo = OP_None,
+                         OperandValueProperties Opd2PropInfo = OP_None) const;
 
   /// \return The cost of a shuffle instruction of kind Kind and of type Tp.
   /// The index and subtype parameters are used by the subvector insertion and
@@ -416,6 +431,13 @@ public:
   virtual unsigned getAddressComputationCost(Type *Ty,
                                              bool IsComplex = false) const;
 
+  /// \returns The cost, if any, of keeping values of the given types alive
+  /// over a callsite.
+  ///
+  /// Some types may require the use of register classes that do not have
+  /// any callee-saved registers, so would require a spill and fill.
+  virtual unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type*> Tys) const;
+
   /// @}
 
   /// Analysis group identification.
diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h
index 83b5408fb1c2..cc588381727d 100644
--- a/include/llvm/Analysis/ValueTracking.h
+++ b/include/llvm/Analysis/ValueTracking.h
@@ -25,6 +25,8 @@ namespace llvm {
   class DataLayout;
   class StringRef;
   class MDNode;
+  class AssumptionCache;
+  class DominatorTree;
   class TargetLibraryInfo;
 
   /// Determine which bits of V are known to be either zero or one and return
@@ -35,8 +37,11 @@ namespace llvm {
   /// 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);
+  void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
+                        const DataLayout *TD = nullptr, unsigned Depth = 0,
+                        AssumptionCache *AC = nullptr,
+                        const Instruction *CxtI = nullptr,
+                        const DominatorTree *DT = nullptr);
   /// Compute known bits from the range metadata.
   /// \p KnownZero the set of bits that are known to be zero
   void computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
@@ -45,21 +50,29 @@ namespace llvm {
   /// 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 *TD = nullptr, unsigned Depth = 0,
+                      AssumptionCache *AC = nullptr,
+                      const Instruction *CxtI = nullptr,
+                      const DominatorTree *DT = nullptr);
 
   /// isKnownToBeAPowerOfTwo - Return true if the given value is known to have
   /// exactly one bit set when defined. For vectors return true if every
   /// 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, bool OrZero = false, unsigned Depth = 0,
+                              AssumptionCache *AC = nullptr,
+                              const Instruction *CxtI = nullptr,
+                              const DominatorTree *DT = nullptr);
 
   /// isKnownNonZero - Return true if the given value is known to be non-zero
   /// 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);
+                      unsigned Depth = 0, AssumptionCache *AC = nullptr,
+                      const Instruction *CxtI = nullptr,
+                      const DominatorTree *DT = nullptr);
 
   /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
   /// this predicate to simplify operations downstream.  Mask is known to be
@@ -70,10 +83,12 @@ namespace llvm {
   /// 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);
+  bool MaskedValueIsZero(Value *V, const APInt &Mask,
+                         const DataLayout *TD = nullptr, unsigned Depth = 0,
+                         AssumptionCache *AC = nullptr,
+                         const Instruction *CxtI = nullptr,
+                         const DominatorTree *DT = nullptr);
 
-  
   /// ComputeNumSignBits - Return the number of times the sign bit of the
   /// register is replicated into the other bits.  We know that at least 1 bit
   /// is always equal to the sign bit (itself), but other cases can give us
@@ -83,7 +98,9 @@ namespace llvm {
   /// 'Op' must have a scalar integer type.
   ///
   unsigned ComputeNumSignBits(Value *Op, const DataLayout *TD = nullptr,
-                              unsigned Depth = 0);
+                              unsigned Depth = 0, AssumptionCache *AC = nullptr,
+                              const Instruction *CxtI = nullptr,
+                              const DominatorTree *DT = nullptr);
 
   /// ComputeMultiple - This function computes the integer multiple of Base that
   /// equals V.  If successful, it returns true and returns the multiple in
@@ -191,6 +208,24 @@ namespace llvm {
   /// and byval arguments.
   bool isKnownNonNull(const Value *V, 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,
+                                               AssumptionCache *AC,
+                                               const Instruction *CxtI,
+                                               const DominatorTree *DT);
+  OverflowResult computeOverflowForUnsignedAdd(Value *LHS, Value *RHS,
+                                               const DataLayout *DL,
+                                               AssumptionCache *AC,
+                                               const Instruction *CxtI,
+                                               const DominatorTree *DT);
 } // end namespace llvm
 
 #endif