vendor/llvm/llvm-trunk-r321017

74 files changed, 1441 insertions, 602 deletions

diff --git a/include/llvm/Transforms/IPO.h b/include/llvm/Transforms/IPO.h
index 39ceb19525b3c..ce20a726b7832 100644
--- a/include/llvm/Transforms/IPO.h
+++ b/include/llvm/Transforms/IPO.h
@@ -216,6 +216,10 @@ ModulePass *createMetaRenamerPass();
 /// manager.
 ModulePass *createBarrierNoopPass();
 
+/// createCalledValuePropagationPass - Attach metadata to indirct call sites
+/// indicating the set of functions they may target at run-time.
+ModulePass *createCalledValuePropagationPass();
+
 /// What to do with the summary when running passes that operate on it.
 enum class PassSummaryAction {
   None,   ///< Do nothing.
diff --git a/include/llvm/Transforms/IPO/ArgumentPromotion.h b/include/llvm/Transforms/IPO/ArgumentPromotion.h
index 724ff72f3b5a1..82ffc69a166ee 100644
--- a/include/llvm/Transforms/IPO/ArgumentPromotion.h
+++ b/include/llvm/Transforms/IPO/ArgumentPromotion.h
@@ -12,6 +12,7 @@
 
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/LazyCallGraph.h"
+#include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
@@ -26,6 +27,6 @@ public:
                         LazyCallGraph &CG, CGSCCUpdateResult &UR);
 };
 
-}
+} // end namespace llvm
 
-#endif
+#endif // LLVM_TRANSFORMS_IPO_ARGUMENTPROMOTION_H
diff --git a/include/llvm/Transforms/IPO/CalledValuePropagation.h b/include/llvm/Transforms/IPO/CalledValuePropagation.h
new file mode 100644
index 0000000000000..352bdc7ac17f1
--- /dev/null
+++ b/include/llvm/Transforms/IPO/CalledValuePropagation.h
@@ -0,0 +1,35 @@
+//===- CalledValuePropagation.h - Propagate called values -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a transformation that attaches !callees metadata to
+// indirect call sites. For a given call site, the metadata, if present,
+// indicates the set of functions the call site could possibly target at
+// run-time. This metadata is added to indirect call sites when the set of
+// possible targets can be determined by analysis and is known to be small. The
+// analysis driving the transformation is similar to constant propagation and
+// makes uses of the generic sparse propagation solver.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_CALLEDVALUEPROPAGATION_H
+#define LLVM_TRANSFORMS_IPO_CALLEDVALUEPROPAGATION_H
+
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+class CalledValuePropagationPass
+    : public PassInfoMixin<CalledValuePropagationPass> {
+public:
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
+};
+} // namespace llvm
+
+#endif // LLVM_TRANSFORMS_IPO_CALLEDVALUEPROPAGATION_H
diff --git a/include/llvm/Transforms/IPO/ConstantMerge.h b/include/llvm/Transforms/IPO/ConstantMerge.h
index 1d4da43f6a7bb..e04d3ae1a40ed 100644
--- a/include/llvm/Transforms/IPO/ConstantMerge.h
+++ b/include/llvm/Transforms/IPO/ConstantMerge.h
@@ -20,16 +20,18 @@
 #ifndef LLVM_TRANSFORMS_IPO_CONSTANTMERGE_H
 #define LLVM_TRANSFORMS_IPO_CONSTANTMERGE_H
 
-#include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
+class Module;
+
 /// A pass that merges duplicate global constants into a single constant.
 class ConstantMergePass : public PassInfoMixin<ConstantMergePass> {
 public:
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
 };
-}
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_CONSTANTMERGE_H
diff --git a/include/llvm/Transforms/IPO/DeadArgumentElimination.h b/include/llvm/Transforms/IPO/DeadArgumentElimination.h
index e179afa956f6e..ba5666f20a9bf 100644
--- a/include/llvm/Transforms/IPO/DeadArgumentElimination.h
+++ b/include/llvm/Transforms/IPO/DeadArgumentElimination.h
@@ -20,15 +20,21 @@
 #ifndef LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
 #define LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
 
-#include "llvm/IR/Module.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
-
 #include <map>
 #include <set>
 #include <string>
+#include <tuple>
 
 namespace llvm {
 
+class Module;
+class Use;
+class Value;
+
 /// Eliminate dead arguments (and return values) from functions.
 class DeadArgumentEliminationPass
     : public PassInfoMixin<DeadArgumentEliminationPass> {
@@ -37,12 +43,13 @@ public:
   /// argument.  Used so that arguments and return values can be used
   /// interchangeably.
   struct RetOrArg {
-    RetOrArg(const Function *F, unsigned Idx, bool IsArg)
-        : F(F), Idx(Idx), IsArg(IsArg) {}
     const Function *F;
     unsigned Idx;
     bool IsArg;
 
+    RetOrArg(const Function *F, unsigned Idx, bool IsArg)
+        : F(F), Idx(Idx), IsArg(IsArg) {}
+
     /// Make RetOrArg comparable, so we can put it into a map.
     bool operator<(const RetOrArg &O) const {
       return std::tie(F, Idx, IsArg) < std::tie(O.F, O.Idx, O.IsArg);
@@ -67,16 +74,23 @@ public:
   /// thus become dead in the end.
   enum Liveness { Live, MaybeLive };
 
+  DeadArgumentEliminationPass(bool ShouldHackArguments_ = false)
+      : ShouldHackArguments(ShouldHackArguments_) {}
+
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
+
   /// Convenience wrapper
   RetOrArg CreateRet(const Function *F, unsigned Idx) {
     return RetOrArg(F, Idx, false);
   }
+
   /// Convenience wrapper
   RetOrArg CreateArg(const Function *F, unsigned Idx) {
     return RetOrArg(F, Idx, true);
   }
 
-  typedef std::multimap<RetOrArg, RetOrArg> UseMap;
+  using UseMap = std::multimap<RetOrArg, RetOrArg>;
+
   /// This maps a return value or argument to any MaybeLive return values or
   /// arguments it uses. This allows the MaybeLive values to be marked live
   /// when any of its users is marked live.
@@ -93,25 +107,21 @@ public:
   ///    directly to F.
   UseMap Uses;
 
-  typedef std::set<RetOrArg> LiveSet;
-  typedef std::set<const Function *> LiveFuncSet;
+  using LiveSet = std::set<RetOrArg>;
+  using LiveFuncSet = std::set<const Function *>;
 
   /// This set contains all values that have been determined to be live.
   LiveSet LiveValues;
+
   /// This set contains all values that are cannot be changed in any way.
   LiveFuncSet LiveFunctions;
 
-  typedef SmallVector<RetOrArg, 5> UseVector;
+  using UseVector = SmallVector<RetOrArg, 5>;
 
   /// This allows this pass to do double-duty as the dead arg hacking pass
   /// (used only by bugpoint).
   bool ShouldHackArguments = false;
 
-public:
-  DeadArgumentEliminationPass(bool ShouldHackArguments_ = false)
-      : ShouldHackArguments(ShouldHackArguments_) {}
-  PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
-
 private:
   Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses);
   Liveness SurveyUse(const Use *U, UseVector &MaybeLiveUses,
@@ -128,6 +138,7 @@ private:
   bool DeleteDeadVarargs(Function &Fn);
   bool RemoveDeadArgumentsFromCallers(Function &Fn);
 };
-}
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
diff --git a/include/llvm/Transforms/IPO/ElimAvailExtern.h b/include/llvm/Transforms/IPO/ElimAvailExtern.h
index 88a0e9bd8ce0f..94cb954fd2d5a 100644
--- a/include/llvm/Transforms/IPO/ElimAvailExtern.h
+++ b/include/llvm/Transforms/IPO/ElimAvailExtern.h
@@ -15,17 +15,19 @@
 #ifndef LLVM_TRANSFORMS_IPO_ELIMAVAILEXTERN_H
 #define LLVM_TRANSFORMS_IPO_ELIMAVAILEXTERN_H
 
-#include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
+class Module;
+
 /// A pass that transforms external global definitions into declarations.
 class EliminateAvailableExternallyPass
     : public PassInfoMixin<EliminateAvailableExternallyPass> {
 public:
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
 };
-}
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_ELIMAVAILEXTERN_H
diff --git a/include/llvm/Transforms/IPO/FunctionAttrs.h b/include/llvm/Transforms/IPO/FunctionAttrs.h
index 36dd06b85b417..dc9f18c794107 100644
--- a/include/llvm/Transforms/IPO/FunctionAttrs.h
+++ b/include/llvm/Transforms/IPO/FunctionAttrs.h
@@ -1,4 +1,4 @@
-//===-- FunctionAttrs.h - Compute function attrs --------------------------===//
+//===- FunctionAttrs.h - Compute function attributes ------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -6,9 +6,11 @@
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
+//
 /// \file
 /// Provides passes for computing function attributes based on interprocedural
 /// analyses.
+//
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H
@@ -21,6 +23,9 @@
 namespace llvm {
 
 class AAResults;
+class Function;
+class Module;
+class Pass;
 
 /// The three kinds of memory access relevant to 'readonly' and
 /// 'readnone' attributes.
@@ -66,6 +71,7 @@ class ReversePostOrderFunctionAttrsPass
 public:
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 };
-}
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H
diff --git a/include/llvm/Transforms/IPO/FunctionImport.h b/include/llvm/Transforms/IPO/FunctionImport.h
index de35cdf052e1f..39e5b5c8ae6f1 100644
--- a/include/llvm/Transforms/IPO/FunctionImport.h
+++ b/include/llvm/Transforms/IPO/FunctionImport.h
@@ -7,23 +7,26 @@
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_FUNCTIONIMPORT_H
-#define LLVM_FUNCTIONIMPORT_H
+#ifndef LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H
+#define LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H
 
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/ModuleSummaryIndex.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Error.h"
-
 #include <functional>
 #include <map>
+#include <memory>
+#include <string>
+#include <system_error>
 #include <unordered_set>
 #include <utility>
 
 namespace llvm {
-class LLVMContext;
-class GlobalValueSummary;
+
 class Module;
 
 /// The function importer is automatically importing function from other modules
@@ -34,19 +37,19 @@ public:
   /// containing all the functions to import for a source module.
   /// The keys is the GUID identifying a function to import, and the value
   /// is the threshold applied when deciding to import it.
-  typedef std::map<GlobalValue::GUID, unsigned> FunctionsToImportTy;
+  using FunctionsToImportTy = std::map<GlobalValue::GUID, unsigned>;
 
   /// The map contains an entry for every module to import from, the key being
   /// the module identifier to pass to the ModuleLoader. The value is the set of
   /// functions to import.
-  typedef StringMap<FunctionsToImportTy> ImportMapTy;
+  using ImportMapTy = StringMap<FunctionsToImportTy>;
 
   /// The set contains an entry for every global value the module exports.
-  typedef std::unordered_set<GlobalValue::GUID> ExportSetTy;
+  using ExportSetTy = std::unordered_set<GlobalValue::GUID>;
 
   /// A function of this type is used to load modules referenced by the index.
-  typedef std::function<Expected<std::unique_ptr<Module>>(StringRef Identifier)>
-      ModuleLoaderTy;
+  using ModuleLoaderTy =
+      std::function<Expected<std::unique_ptr<Module>>(StringRef Identifier)>;
 
   /// Create a Function Importer.
   FunctionImporter(const ModuleSummaryIndex &Index, ModuleLoaderTy ModuleLoader)
@@ -95,6 +98,15 @@ void ComputeCrossModuleImportForModule(
     StringRef ModulePath, const ModuleSummaryIndex &Index,
     FunctionImporter::ImportMapTy &ImportList);
 
+/// Mark all external summaries in \p Index for import into the given module.
+/// Used for distributed builds using a distributed index.
+///
+/// \p ImportList will be populated with a map that can be passed to
+/// FunctionImporter::importFunctions() above (see description there).
+void ComputeCrossModuleImportForModuleFromIndex(
+    StringRef ModulePath, const ModuleSummaryIndex &Index,
+    FunctionImporter::ImportMapTy &ImportList);
+
 /// Compute all the symbols that are "dead": i.e these that can't be reached
 /// in the graph from any of the given symbols listed in
 /// \p GUIDPreservedSymbols.
@@ -132,6 +144,7 @@ void thinLTOResolveWeakForLinkerModule(Module &TheModule,
 /// during global summary-based analysis.
 void thinLTOInternalizeModule(Module &TheModule,
                               const GVSummaryMapTy &DefinedGlobals);
-}
 
-#endif // LLVM_FUNCTIONIMPORT_H
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H
diff --git a/include/llvm/Transforms/IPO/GlobalDCE.h b/include/llvm/Transforms/IPO/GlobalDCE.h
index 9ca939c15b62e..7ca241f4645a9 100644
--- a/include/llvm/Transforms/IPO/GlobalDCE.h
+++ b/include/llvm/Transforms/IPO/GlobalDCE.h
@@ -35,7 +35,7 @@ private:
   SmallPtrSet<GlobalValue*, 32> AliveGlobals;
 
   /// Global -> Global that uses this global.
-  std::unordered_multimap<GlobalValue *, GlobalValue *> GVDependencies;
+  DenseMap<GlobalValue *, SmallPtrSet<GlobalValue *, 4>> GVDependencies;
 
   /// Constant -> Globals that use this global cache.
   std::unordered_map<Constant *, SmallPtrSet<GlobalValue *, 8>>
diff --git a/include/llvm/Transforms/IPO/GlobalOpt.h b/include/llvm/Transforms/IPO/GlobalOpt.h
index ab9116810be1b..5b4878604eab1 100644
--- a/include/llvm/Transforms/IPO/GlobalOpt.h
+++ b/include/llvm/Transforms/IPO/GlobalOpt.h
@@ -16,17 +16,18 @@
 #ifndef LLVM_TRANSFORMS_IPO_GLOBALOPT_H
 #define LLVM_TRANSFORMS_IPO_GLOBALOPT_H
 
-#include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
+class Module;
+
 /// Optimize globals that never have their address taken.
 class GlobalOptPass : public PassInfoMixin<GlobalOptPass> {
 public:
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 };
 
-}
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_GLOBALOPT_H
diff --git a/include/llvm/Transforms/IPO/GlobalSplit.h b/include/llvm/Transforms/IPO/GlobalSplit.h
index fb2c2d27338e0..56cefb7886fec 100644
--- a/include/llvm/Transforms/IPO/GlobalSplit.h
+++ b/include/llvm/Transforms/IPO/GlobalSplit.h
@@ -17,14 +17,18 @@
 #ifndef LLVM_TRANSFORMS_IPO_GLOBALSPLIT_H
 #define LLVM_TRANSFORMS_IPO_GLOBALSPLIT_H
 
-#include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
+
+class Module;
+
 /// Pass to perform split of global variables.
 class GlobalSplitPass : public PassInfoMixin<GlobalSplitPass> {
 public:
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 };
-}
+
+} // end namespace llvm
+
 #endif // LLVM_TRANSFORMS_IPO_GLOBALSPLIT_H
diff --git a/include/llvm/Transforms/IPO/Inliner.h b/include/llvm/Transforms/IPO/Inliner.h
index b3ca5156e3883..eda8cf462b507 100644
--- a/include/llvm/Transforms/IPO/Inliner.h
+++ b/include/llvm/Transforms/IPO/Inliner.h
@@ -14,15 +14,15 @@
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LazyCallGraph.h"
-#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/PassManager.h"
 #include "llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h"
+#include <utility>
 
 namespace llvm {
+
 class AssumptionCacheTracker;
-class CallSite;
-class DataLayout;
-class InlineCost;
-class OptimizationRemarkEmitter;
+class CallGraph;
 class ProfileSummaryInfo;
 
 /// This class contains all of the helper code which is used to perform the
@@ -44,6 +44,7 @@ struct LegacyInlinerBase : public CallGraphSCCPass {
   bool runOnSCC(CallGraphSCC &SCC) override;
 
   using llvm::Pass::doFinalization;
+
   /// Remove now-dead linkonce functions at the end of processing to avoid
   /// breaking the SCC traversal.
   bool doFinalization(CallGraph &CG) override;
@@ -69,7 +70,7 @@ struct LegacyInlinerBase : public CallGraphSCCPass {
 
 private:
   // Insert @llvm.lifetime intrinsics.
-  bool InsertLifetime;
+  bool InsertLifetime = true;
 
 protected:
   AssumptionCacheTracker *ACT;
@@ -103,6 +104,6 @@ private:
   InlineParams Params;
 };
 
-} // End llvm namespace
+} // end namespace llvm
 
-#endif
+#endif // LLVM_TRANSFORMS_IPO_INLINER_H
diff --git a/include/llvm/Transforms/IPO/LowerTypeTests.h b/include/llvm/Transforms/IPO/LowerTypeTests.h
index a2b888ce9ffa3..3bcfe65df5502 100644
--- a/include/llvm/Transforms/IPO/LowerTypeTests.h
+++ b/include/llvm/Transforms/IPO/LowerTypeTests.h
@@ -16,7 +16,6 @@
 #define LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H
 
 #include "llvm/ADT/SmallVector.h"
-#include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 #include <cstdint>
 #include <cstring>
@@ -26,6 +25,7 @@
 
 namespace llvm {
 
+class Module;
 class raw_ostream;
 
 namespace lowertypetests {
diff --git a/include/llvm/Transforms/IPO/PartialInlining.h b/include/llvm/Transforms/IPO/PartialInlining.h
index 15407fc36a225..ec6dd36dae06e 100644
--- a/include/llvm/Transforms/IPO/PartialInlining.h
+++ b/include/llvm/Transforms/IPO/PartialInlining.h
@@ -1,4 +1,4 @@
-//===- PartialInlining.h - Inline parts of functions --------------------===//
+//===- PartialInlining.h - Inline parts of functions ------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -15,15 +15,18 @@
 #ifndef LLVM_TRANSFORMS_IPO_PARTIALINLINING_H
 #define LLVM_TRANSFORMS_IPO_PARTIALINLINING_H
 
-#include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
+class Module;
+
 /// Pass to remove unused function declarations.
 class PartialInlinerPass : public PassInfoMixin<PartialInlinerPass> {
 public:
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
 };
-}
+
+} // end namespace llvm
+
 #endif // LLVM_TRANSFORMS_IPO_PARTIALINLINING_H
diff --git a/include/llvm/Transforms/IPO/SCCP.h b/include/llvm/Transforms/IPO/SCCP.h
index 7082006f14a6f..fdb7865fbac31 100644
--- a/include/llvm/Transforms/IPO/SCCP.h
+++ b/include/llvm/Transforms/IPO/SCCP.h
@@ -21,14 +21,18 @@
 #ifndef LLVM_TRANSFORMS_IPO_SCCP_H
 #define LLVM_TRANSFORMS_IPO_SCCP_H
 
-#include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
+
+class Module;
+
 /// Pass to perform interprocedural constant propagation.
 class IPSCCPPass : public PassInfoMixin<IPSCCPPass> {
 public:
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 };
-}
+
+} // end namespace llvm
+
 #endif // LLVM_TRANSFORMS_IPO_SCCP_H
diff --git a/include/llvm/Transforms/Instrumentation.h b/include/llvm/Transforms/Instrumentation.h
index f2fc6dc8dad5e..cd6b770f76ac0 100644
--- a/include/llvm/Transforms/Instrumentation.h
+++ b/include/llvm/Transforms/Instrumentation.h
@@ -22,24 +22,11 @@
 #include <string>
 #include <vector>
 
-#if defined(__GNUC__) && defined(__linux__) && !defined(ANDROID)
-inline void *getDFSanArgTLSPtrForJIT() {
-  extern __thread __attribute__((tls_model("initial-exec")))
-    void *__dfsan_arg_tls;
-  return (void *)&__dfsan_arg_tls;
-}
-
-inline void *getDFSanRetValTLSPtrForJIT() {
-  extern __thread __attribute__((tls_model("initial-exec")))
-    void *__dfsan_retval_tls;
-  return (void *)&__dfsan_retval_tls;
-}
-#endif
-
 namespace llvm {
 
 class FunctionPass;
 class ModulePass;
+class OptimizationRemarkEmitter;
 
 /// Instrumentation passes often insert conditional checks into entry blocks.
 /// Call this function before splitting the entry block to move instructions
@@ -90,9 +77,12 @@ ModulePass *createPGOIndirectCallPromotionLegacyPass(bool InLTO = false,
                                                      bool SamplePGO = false);
 FunctionPass *createPGOMemOPSizeOptLegacyPass();
 
-// Helper function to check if it is legal to promote indirect call \p Inst
-// to a direct call of function \p F. Stores the reason in \p Reason.
-bool isLegalToPromote(Instruction *Inst, Function *F, const char **Reason);
+// The pgo-specific indirect call promotion function declared below is used by
+// the pgo-driven indirect call promotion and sample profile passes. It's a
+// wrapper around llvm::promoteCall, et al. that additionally computes !prof
+// metadata. We place it in a pgo namespace so it's not confused with the
+// generic utilities.
+namespace pgo {
 
 // Helper function that transforms Inst (either an indirect-call instruction, or
 // an invoke instruction , to a conditional call to F. This is like:
@@ -109,7 +99,9 @@ bool isLegalToPromote(Instruction *Inst, Function *F, const char **Reason);
 // Returns the promoted direct call instruction.
 Instruction *promoteIndirectCall(Instruction *Inst, Function *F, uint64_t Count,
                                  uint64_t TotalCount,
-                                 bool AttachProfToDirectCall);
+                                 bool AttachProfToDirectCall,
+                                 OptimizationRemarkEmitter *ORE);
+} // namespace pgo
 
 /// Options for the frontend instrumentation based profiling pass.
 struct InstrProfOptions {
@@ -141,6 +133,8 @@ ModulePass *createAddressSanitizerModulePass(bool CompileKernel = false,
 FunctionPass *createMemorySanitizerPass(int TrackOrigins = 0,
                                         bool Recover = false);
 
+FunctionPass *createHWAddressSanitizerPass();
+
 // Insert ThreadSanitizer (race detection) instrumentation
 FunctionPass *createThreadSanitizerPass();
 
@@ -181,7 +175,9 @@ struct SanitizerCoverageOptions {
   bool TracePC = false;
   bool TracePCGuard = false;
   bool Inline8bitCounters = false;
+  bool PCTable = false;
   bool NoPrune = false;
+  bool StackDepth = false;
 
   SanitizerCoverageOptions() = default;
 };
@@ -190,18 +186,6 @@ struct SanitizerCoverageOptions {
 ModulePass *createSanitizerCoverageModulePass(
     const SanitizerCoverageOptions &Options = SanitizerCoverageOptions());
 
-#if defined(__GNUC__) && defined(__linux__) && !defined(ANDROID)
-inline ModulePass *createDataFlowSanitizerPassForJIT(
-    const std::vector<std::string> &ABIListFiles = std::vector<std::string>()) {
-  return createDataFlowSanitizerPass(ABIListFiles, getDFSanArgTLSPtrForJIT,
-                                     getDFSanRetValTLSPtrForJIT);
-}
-#endif
-
-// BoundsChecking - This pass instruments the code to perform run-time bounds
-// checking on loads, stores, and other memory intrinsics.
-FunctionPass *createBoundsCheckingPass();
-
 /// \brief Calculate what to divide by to scale counts.
 ///
 /// Given the maximum count, calculate a divisor that will scale all the
diff --git a/include/llvm/Transforms/Instrumentation/BoundsChecking.h b/include/llvm/Transforms/Instrumentation/BoundsChecking.h
new file mode 100644
index 0000000000000..3d4f62c121c25
--- /dev/null
+++ b/include/llvm/Transforms/Instrumentation/BoundsChecking.h
@@ -0,0 +1,29 @@
+//===- BoundsChecking.h - Bounds checking instrumentation -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_INSTRUMENTATION_BOUNDSCHECKING_H
+#define LLVM_TRANSFORMS_INSTRUMENTATION_BOUNDSCHECKING_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+/// A pass to instrument code and perform run-time bounds checking on loads,
+/// stores, and other memory intrinsics.
+struct BoundsCheckingPass : PassInfoMixin<BoundsCheckingPass> {
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
+
+/// Legacy pass creation function for the above pass.
+FunctionPass *createBoundsCheckingLegacyPass();
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_INSTRUMENTATION_BOUNDSCHECKING_H
diff --git a/include/llvm/Transforms/PGOInstrumentation.h b/include/llvm/Transforms/PGOInstrumentation.h
index 19263f0f8071d..c2cc76c422dae 100644
--- a/include/llvm/Transforms/PGOInstrumentation.h
+++ b/include/llvm/Transforms/PGOInstrumentation.h
@@ -1,4 +1,4 @@
-//===- Transforms/PGOInstrumentation.h - PGO gen/use passes  ---*- C++ -*-===//
+//===- Transforms/PGOInstrumentation.h - PGO gen/use passes -----*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -6,19 +6,27 @@
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
+//
 /// \file
 /// This file provides the interface for IR based instrumentation passes (
 /// (profile-gen, and profile-use).
+//
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_PGOINSTRUMENTATION_H
 #define LLVM_TRANSFORMS_PGOINSTRUMENTATION_H
 
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/IR/PassManager.h"
-#include "llvm/Transforms/Instrumentation.h"
+#include <cstdint>
+#include <string>
 
 namespace llvm {
 
+class Function;
+class Instruction;
+class Module;
+
 /// The instrumentation (profile-instr-gen) pass for IR based PGO.
 class PGOInstrumentationGen : public PassInfoMixin<PGOInstrumentationGen> {
 public:
@@ -28,9 +36,10 @@ public:
 /// The profile annotation (profile-instr-use) pass for IR based PGO.
 class PGOInstrumentationUse : public PassInfoMixin<PGOInstrumentationUse> {
 public:
-  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
   PGOInstrumentationUse(std::string Filename = "");
 
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
+
 private:
   std::string ProfileFileName;
 };
@@ -40,6 +49,7 @@ class PGOIndirectCallPromotion : public PassInfoMixin<PGOIndirectCallPromotion>
 public:
   PGOIndirectCallPromotion(bool IsInLTO = false, bool SamplePGO = false)
       : InLTO(IsInLTO), SamplePGO(SamplePGO) {}
+
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 
 private:
@@ -50,12 +60,16 @@ private:
 /// The profile size based optimization pass for memory intrinsics.
 class PGOMemOPSizeOpt : public PassInfoMixin<PGOMemOPSizeOpt> {
 public:
-  PGOMemOPSizeOpt() {}
+  PGOMemOPSizeOpt() = default;
+
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
 void setProfMetadata(Module *M, Instruction *TI, ArrayRef<uint64_t> EdgeCounts,
                      uint64_t MaxCount);
 
-} // End llvm namespace
-#endif
+void setIrrLoopHeaderMetadata(Module *M, Instruction *TI, uint64_t Count);
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_PGOINSTRUMENTATION_H
diff --git a/include/llvm/Transforms/SampleProfile.h b/include/llvm/Transforms/SampleProfile.h
index c984fe74ba939..f5a8590e14a1c 100644
--- a/include/llvm/Transforms/SampleProfile.h
+++ b/include/llvm/Transforms/SampleProfile.h
@@ -1,4 +1,4 @@
-//===- Transforms/SampleProfile.h - SamplePGO pass--------------*- C++ -*-===//
+//===- Transforms/SampleProfile.h - SamplePGO pass --------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -6,26 +6,35 @@
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
+//
 /// \file
 /// This file provides the interface for the sampled PGO loader pass.
+//
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SAMPLEPROFILE_H
 #define LLVM_TRANSFORMS_SAMPLEPROFILE_H
 
 #include "llvm/IR/PassManager.h"
+#include <string>
 
 namespace llvm {
 
+class Module;
+
 /// The sample profiler data loader pass.
 class SampleProfileLoaderPass : public PassInfoMixin<SampleProfileLoaderPass> {
 public:
+  SampleProfileLoaderPass(std::string File = "", bool IsThinLTOPreLink = false)
+      : ProfileFileName(File), IsThinLTOPreLink(IsThinLTOPreLink) {}
+
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
-  SampleProfileLoaderPass(std::string File = "") : ProfileFileName(File) {}
 
 private:
   std::string ProfileFileName;
+  bool IsThinLTOPreLink;
 };
 
-} // End llvm namespace
-#endif
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_SAMPLEPROFILE_H
diff --git a/include/llvm/Transforms/Scalar.h b/include/llvm/Transforms/Scalar.h
index 1913a9d5da027..49186bc5cd666 100644
--- a/include/llvm/Transforms/Scalar.h
+++ b/include/llvm/Transforms/Scalar.h
@@ -73,6 +73,14 @@ FunctionPass *createDeadCodeEliminationPass();
 //
 FunctionPass *createDeadStoreEliminationPass();
 
+
+//===----------------------------------------------------------------------===//
+//
+// CallSiteSplitting - This pass split call-site based on its known argument
+// values.
+FunctionPass *createCallSiteSplittingPass();
+
+
 //===----------------------------------------------------------------------===//
 //
 // AggressiveDCE - This pass uses the SSA based Aggressive DCE algorithm.  This
@@ -184,7 +192,7 @@ Pass *createLoopInstSimplifyPass();
 //
 Pass *createLoopUnrollPass(int OptLevel = 2, int Threshold = -1, int Count = -1,
                            int AllowPartial = -1, int Runtime = -1,
-                           int UpperBound = -1);
+                           int UpperBound = -1, int AllowPeeling = -1);
 // Create an unrolling pass for full unrolling that uses exact trip count only.
 Pass *createSimpleLoopUnrollPass(int OptLevel = 2);
 
@@ -255,18 +263,12 @@ FunctionPass *createJumpThreadingPass(int Threshold = -1);
 //===----------------------------------------------------------------------===//
 //
 // CFGSimplification - Merge basic blocks, eliminate unreachable blocks,
-// simplify terminator instructions, etc...
+// simplify terminator instructions, convert switches to lookup tables, etc.
 //
 FunctionPass *createCFGSimplificationPass(
-    int Threshold = -1, std::function<bool(const Function &)> Ftor = nullptr);
-
-//===----------------------------------------------------------------------===//
-//
-// LateCFGSimplification - Like CFGSimplification, but may also
-// convert switches to lookup tables.
-//
-FunctionPass *createLateCFGSimplificationPass(
-    int Threshold = -1, std::function<bool(const Function &)> Ftor = nullptr);
+    unsigned Threshold = 1, bool ForwardSwitchCond = false,
+    bool ConvertSwitch = false, bool KeepLoops = true, bool SinkCommon = false,
+    std::function<bool(const Function &)> Ftor = nullptr);
 
 //===----------------------------------------------------------------------===//
 //
@@ -377,6 +379,12 @@ FunctionPass *createNewGVNPass();
 
 //===----------------------------------------------------------------------===//
 //
+// DivRemPairs - Hoist/decompose integer division and remainder instructions.
+//
+FunctionPass *createDivRemPairsPass();
+
+//===----------------------------------------------------------------------===//
+//
 // MemCpyOpt - This pass performs optimizations related to eliminating memcpy
 // calls and/or combining multiple stores into memset's.
 //
@@ -422,6 +430,12 @@ Pass *createLowerGuardIntrinsicPass();
 
 //===----------------------------------------------------------------------===//
 //
+// MergeICmps - Merge integer comparison chains into a memcmp
+//
+Pass *createMergeICmpsPass();
+
+//===----------------------------------------------------------------------===//
+//
 // ValuePropagation - Propagate CFG-derived value information
 //
 Pass *createCorrelatedValuePropagationPass();
@@ -507,7 +521,7 @@ FunctionPass *createPlaceSafepointsPass();
 // RewriteStatepointsForGC - Rewrite any gc.statepoints which do not yet have
 // explicit relocations to include explicit relocations.
 //
-ModulePass *createRewriteStatepointsForGCPass();
+ModulePass *createRewriteStatepointsForGCLegacyPass();
 
 //===----------------------------------------------------------------------===//
 //
@@ -568,6 +582,16 @@ ModulePass *createNameAnonGlobalPass();
 // used.
 //
 FunctionPass *createLibCallsShrinkWrapPass();
+
+//===----------------------------------------------------------------------===//
+//
+// EntryExitInstrumenter pass - Instrument function entry/exit with calls to
+// mcount(), @__cyg_profile_func_{enter,exit} and the like. There are two
+// variants, intended to run pre- and post-inlining, respectively.
+//
+FunctionPass *createEntryExitInstrumenterPass();
+FunctionPass *createPostInlineEntryExitInstrumenterPass();
+
 } // End llvm namespace
 
 #endif
diff --git a/include/llvm/Transforms/Scalar/ADCE.h b/include/llvm/Transforms/Scalar/ADCE.h
index b9b7e1c0c99fd..f98af62c1a76f 100644
--- a/include/llvm/Transforms/Scalar/ADCE.h
+++ b/include/llvm/Transforms/Scalar/ADCE.h
@@ -1,4 +1,4 @@
-//===- ADCE.h - Aggressive dead code elimination --------------------------===//
+//===- ADCE.h - Aggressive dead code elimination ----------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -17,11 +17,12 @@
 #ifndef LLVM_TRANSFORMS_SCALAR_ADCE_H
 #define LLVM_TRANSFORMS_SCALAR_ADCE_H
 
-#include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
+class Function;
+
 /// A DCE pass that assumes instructions are dead until proven otherwise.
 ///
 /// This pass eliminates dead code by optimistically assuming that all
@@ -31,6 +32,7 @@ namespace llvm {
 struct ADCEPass : PassInfoMixin<ADCEPass> {
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
 };
-}
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_ADCE_H
diff --git a/include/llvm/Transforms/Scalar/CallSiteSplitting.h b/include/llvm/Transforms/Scalar/CallSiteSplitting.h
new file mode 100644
index 0000000000000..5ab951a49f2c8
--- /dev/null
+++ b/include/llvm/Transforms/Scalar/CallSiteSplitting.h
@@ -0,0 +1,29 @@
+//===- CallSiteSplitting..h - Callsite Splitting ------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_CALLSITESPLITTING__H
+#define LLVM_TRANSFORMS_SCALAR_CALLSITESPLITTING__H
+
+#include "llvm/ADT/SetVector.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Support/Compiler.h"
+#include <vector>
+
+namespace llvm {
+
+struct CallSiteSplittingPass : PassInfoMixin<CallSiteSplittingPass> {
+  /// \brief Run the pass over the function.
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_SCALAR_CALLSITESPLITTING__H
diff --git a/include/llvm/Transforms/Scalar/ConstantHoisting.h b/include/llvm/Transforms/Scalar/ConstantHoisting.h
index a2a9afc083a0b..d3322dc1c414a 100644
--- a/include/llvm/Transforms/Scalar/ConstantHoisting.h
+++ b/include/llvm/Transforms/Scalar/ConstantHoisting.h
@@ -1,4 +1,4 @@
-//===-- ConstantHoisting.h - Prepare code for expensive constants ---------===//
+//==- ConstantHoisting.h - Prepare code for expensive constants --*- C++ -*-==//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -31,41 +31,53 @@
 // This optimization is only applied to integer constants in instructions and
 // simple (this means not nested) constant cast expressions. For example:
 // %0 = load i64* inttoptr (i64 big_constant to i64*)
+//
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
 #define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
 
-#include "llvm/Analysis/BlockFrequencyInfo.h"
-#include "llvm/Analysis/TargetTransformInfo.h"
-#include "llvm/IR/Dominators.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/PassManager.h"
+#include <algorithm>
+#include <vector>
 
 namespace llvm {
 
+class BasicBlock;
+class BlockFrequencyInfo;
+class Constant;
+class ConstantInt;
+class DominatorTree;
+class Function;
+class Instruction;
+class TargetTransformInfo;
+
 /// A private "module" namespace for types and utilities used by
 /// ConstantHoisting. These are implementation details and should not be used by
 /// clients.
 namespace consthoist {
+
 /// \brief Keeps track of the user of a constant and the operand index where the
 /// constant is used.
 struct ConstantUser {
   Instruction *Inst;
   unsigned OpndIdx;
 
-  ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) { }
+  ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
 };
 
-typedef SmallVector<ConstantUser, 8> ConstantUseListType;
+using ConstantUseListType = SmallVector<ConstantUser, 8>;
 
 /// \brief Keeps track of a constant candidate and its uses.
 struct ConstantCandidate {
   ConstantUseListType Uses;
   ConstantInt *ConstInt;
-  unsigned CumulativeCost;
+  unsigned CumulativeCost = 0;
 
-  ConstantCandidate(ConstantInt *ConstInt)
-    : ConstInt(ConstInt), CumulativeCost(0) { }
+  ConstantCandidate(ConstantInt *ConstInt) : ConstInt(ConstInt) {}
 
   /// \brief Add the user to the use list and update the cost.
   void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
@@ -81,17 +93,18 @@ struct RebasedConstantInfo {
   Constant *Offset;
 
   RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
-    : Uses(std::move(Uses)), Offset(Offset) { }
+    : Uses(std::move(Uses)), Offset(Offset) {}
 };
 
-typedef SmallVector<RebasedConstantInfo, 4> RebasedConstantListType;
+using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>;
 
 /// \brief A base constant and all its rebased constants.
 struct ConstantInfo {
   ConstantInt *BaseConstant;
   RebasedConstantListType RebasedConstants;
 };
-}
+
+} // end namespace consthoist
 
 class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
 public:
@@ -108,8 +121,8 @@ public:
   }
 
 private:
-  typedef DenseMap<ConstantInt *, unsigned> ConstCandMapType;
-  typedef std::vector<consthoist::ConstantCandidate> ConstCandVecType;
+  using ConstCandMapType = DenseMap<ConstantInt *, unsigned>;
+  using ConstCandVecType = std::vector<consthoist::ConstantCandidate>;
 
   const TargetTransformInfo *TTI;
   DominatorTree *DT;
@@ -148,6 +161,7 @@ private:
   void deleteDeadCastInst() const;
   bool optimizeConstants(Function &Fn);
 };
-}
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
diff --git a/include/llvm/Transforms/Scalar/CorrelatedValuePropagation.h b/include/llvm/Transforms/Scalar/CorrelatedValuePropagation.h
index 38816bbed0680..20930699b5578 100644
--- a/include/llvm/Transforms/Scalar/CorrelatedValuePropagation.h
+++ b/include/llvm/Transforms/Scalar/CorrelatedValuePropagation.h
@@ -1,4 +1,4 @@
-//===---- CorrelatedValuePropagation.h --------------------------*- C++ -*-===//
+//===- CorrelatedValuePropagation.h -----------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -10,15 +10,17 @@
 #ifndef LLVM_TRANSFORMS_SCALAR_CORRELATEDVALUEPROPAGATION_H
 #define LLVM_TRANSFORMS_SCALAR_CORRELATEDVALUEPROPAGATION_H
 
-#include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
+class Function;
+
 struct CorrelatedValuePropagationPass
     : PassInfoMixin<CorrelatedValuePropagationPass> {
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
-}
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_CORRELATEDVALUEPROPAGATION_H
diff --git a/include/llvm/Transforms/Scalar/DeadStoreElimination.h b/include/llvm/Transforms/Scalar/DeadStoreElimination.h
index 3ae999dfb5424..cfeb218142321 100644
--- a/include/llvm/Transforms/Scalar/DeadStoreElimination.h
+++ b/include/llvm/Transforms/Scalar/DeadStoreElimination.h
@@ -1,4 +1,4 @@
-//===- DeadStoreElimination.h - Fast Dead Store Elimination -------------===//
+//===- DeadStoreElimination.h - Fast Dead Store Elimination -----*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -15,20 +15,22 @@
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_TRANSFORMS_SCALAR_DSE_H
-#define LLVM_TRANSFORMS_SCALAR_DSE_H
+#ifndef LLVM_TRANSFORMS_SCALAR_DEADSTOREELIMINATION_H
+#define LLVM_TRANSFORMS_SCALAR_DEADSTOREELIMINATION_H
 
-#include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
+class Function;
+
 /// This class implements a trivial dead store elimination. We consider
 /// only the redundant stores that are local to a single Basic Block.
 class DSEPass : public PassInfoMixin<DSEPass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM);
 };
-}
 
-#endif // LLVM_TRANSFORMS_SCALAR_DSE_H
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_SCALAR_DEADSTOREELIMINATION_H
diff --git a/include/llvm/Transforms/Scalar/DivRemPairs.h b/include/llvm/Transforms/Scalar/DivRemPairs.h
new file mode 100644
index 0000000000000..0a4346f33b12b
--- /dev/null
+++ b/include/llvm/Transforms/Scalar/DivRemPairs.h
@@ -0,0 +1,31 @@
+//===- DivRemPairs.h - Hoist/decompose integer division and remainder -----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass hoists and/or decomposes integer division and remainder
+// instructions to enable CFG improvements and better codegen.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_DIVREMPAIRS_H
+#define LLVM_TRANSFORMS_SCALAR_DIVREMPAIRS_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+/// Hoist/decompose integer division and remainder instructions to enable CFG
+/// improvements and better codegen.
+struct DivRemPairsPass : public PassInfoMixin<DivRemPairsPass> {
+public:
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
+};
+
+}
+#endif // LLVM_TRANSFORMS_SCALAR_DIVREMPAIRS_H
+
diff --git a/include/llvm/Transforms/Scalar/EarlyCSE.h b/include/llvm/Transforms/Scalar/EarlyCSE.h
index 969ab78bfd19f..dca3b2dbf04f4 100644
--- a/include/llvm/Transforms/Scalar/EarlyCSE.h
+++ b/include/llvm/Transforms/Scalar/EarlyCSE.h
@@ -6,19 +6,21 @@
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
+//
 /// \file
 /// This file provides the interface for a simple, fast CSE pass.
-///
+//
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_EARLYCSE_H
 #define LLVM_TRANSFORMS_SCALAR_EARLYCSE_H
 
-#include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
+class Function;
+
 /// \brief A simple and fast domtree-based CSE pass.
 ///
 /// This pass does a simple depth-first walk over the dominator tree,
@@ -35,6 +37,6 @@ struct EarlyCSEPass : PassInfoMixin<EarlyCSEPass> {
   bool UseMemorySSA;
 };
 
-}
+} // end namespace llvm
 
-#endif
+#endif // LLVM_TRANSFORMS_SCALAR_EARLYCSE_H
diff --git a/include/llvm/Transforms/Scalar/GVN.h b/include/llvm/Transforms/Scalar/GVN.h
index f25ab40640dfc..440d3f67c35a7 100644
--- a/include/llvm/Transforms/Scalar/GVN.h
+++ b/include/llvm/Transforms/Scalar/GVN.h
@@ -18,26 +18,48 @@
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
-#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
-#include "llvm/Analysis/AssumptionCache.h"
-#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/IR/Dominators.h"
-#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Transforms/Utils/OrderedInstructions.h"
+#include <cstdint>
+#include <utility>
+#include <vector>
 
 namespace llvm {
+
+class AssumptionCache;
+class BasicBlock;
+class BranchInst;
+class CallInst;
+class Constant;
+class ExtractValueInst;
+class Function;
+class FunctionPass;
+class IntrinsicInst;
+class LoadInst;
+class LoopInfo;
 class OptimizationRemarkEmitter;
+class PHINode;
+class TargetLibraryInfo;
+class Value;
 
 /// A private "module" namespace for types and utilities used by GVN. These
 /// are implementation details and should not be used by clients.
 namespace gvn LLVM_LIBRARY_VISIBILITY {
+
 struct AvailableValue;
 struct AvailableValueInBlock;
 class GVNLegacyPass;
-}
+
+} // end namespace gvn
 
 /// The core GVN pass object.
 ///
@@ -45,6 +67,7 @@ class GVNLegacyPass;
 /// this particular pass here.
 class GVN : public PassInfoMixin<GVN> {
 public:
+  struct Expression;
 
   /// \brief Run the pass over the function.
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
@@ -60,25 +83,45 @@ public:
   AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
   MemoryDependenceResults &getMemDep() const { return *MD; }
 
-  struct Expression;
-
   /// This class holds the mapping between values and value numbers.  It is used
   /// as an efficient mechanism to determine the expression-wise equivalence of
   /// two values.
   class ValueTable {
     DenseMap<Value *, uint32_t> valueNumbering;
     DenseMap<Expression, uint32_t> expressionNumbering;
+
+    // Expressions is the vector of Expression. ExprIdx is the mapping from
+    // value number to the index of Expression in Expressions. We use it
+    // instead of a DenseMap because filling such mapping is faster than
+    // filling a DenseMap and the compile time is a little better.
+    uint32_t nextExprNumber;
+
+    std::vector<Expression> Expressions;
+    std::vector<uint32_t> ExprIdx;
+
+    // Value number to PHINode mapping. Used for phi-translate in scalarpre.
+    DenseMap<uint32_t, PHINode *> NumberingPhi;
+
+    // Cache for phi-translate in scalarpre.
+    using PhiTranslateMap =
+        DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>;
+    PhiTranslateMap PhiTranslateTable;
+
     AliasAnalysis *AA;
     MemoryDependenceResults *MD;
     DominatorTree *DT;
 
-    uint32_t nextValueNumber;
+    uint32_t nextValueNumber = 1;
 
     Expression createExpr(Instruction *I);
     Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
                              Value *LHS, Value *RHS);
     Expression createExtractvalueExpr(ExtractValueInst *EI);
     uint32_t lookupOrAddCall(CallInst *C);
+    uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
+                              uint32_t Num, GVN &Gvn);
+    std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
+    bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVN &Gvn);
 
   public:
     ValueTable();
@@ -87,9 +130,12 @@ public:
     ~ValueTable();
 
     uint32_t lookupOrAdd(Value *V);
-    uint32_t lookup(Value *V) const;
+    uint32_t lookup(Value *V, bool Verify = true) const;
     uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
                             Value *LHS, Value *RHS);
+    uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
+                          uint32_t Num, GVN &Gvn);
+    void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
     bool exists(Value *V) const;
     void add(Value *V, uint32_t num);
     void clear();
@@ -112,7 +158,11 @@ private:
   AssumptionCache *AC;
   SetVector<BasicBlock *> DeadBlocks;
   OptimizationRemarkEmitter *ORE;
+  // Maps a block to the topmost instruction with implicit control flow in it.
+  DenseMap<const BasicBlock *, const Instruction *>
+      FirstImplicitControlFlowInsts;
 
+  OrderedInstructions *OI;
   ValueTable VN;
 
   /// A mapping from value numbers to lists of Value*'s that
@@ -128,12 +178,16 @@ private:
   // Block-local map of equivalent values to their leader, does not
   // propagate to any successors. Entries added mid-block are applied
   // to the remaining instructions in the block.
-  SmallMapVector<llvm::Value *, llvm::Constant *, 4> ReplaceWithConstMap;
+  SmallMapVector<Value *, Constant *, 4> ReplaceWithConstMap;
   SmallVector<Instruction *, 8> InstrsToErase;
 
-  typedef SmallVector<NonLocalDepResult, 64> LoadDepVect;
-  typedef SmallVector<gvn::AvailableValueInBlock, 64> AvailValInBlkVect;
-  typedef SmallVector<BasicBlock *, 64> UnavailBlkVect;
+  // Map the block to reversed postorder traversal number. It is used to
+  // find back edge easily.
+  DenseMap<const BasicBlock *, uint32_t> BlockRPONumber;
+
+  using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
+  using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
+  using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
 
   bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
                const TargetLibraryInfo &RunTLI, AAResults &RunAA,
@@ -192,17 +246,20 @@ private:
   bool processLoad(LoadInst *L);
   bool processNonLocalLoad(LoadInst *L);
   bool processAssumeIntrinsic(IntrinsicInst *II);
+
   /// Given a local dependency (Def or Clobber) determine if a value is
   /// available for the load.  Returns true if an value is known to be
   /// available and populates Res.  Returns false otherwise.
   bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
                                Value *Address, gvn::AvailableValue &Res);
+
   /// Given a list of non-local dependencies, determine if a value is
   /// available for the load in each specified block.  If it is, add it to
   /// ValuesPerBlock.  If not, add it to UnavailableBlocks.
   void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
                                AvailValInBlkVect &ValuesPerBlock,
                                UnavailBlkVect &UnavailableBlocks);
+
   bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
                       UnavailBlkVect &UnavailableBlocks);
 
@@ -214,9 +271,10 @@ private:
   bool performPRE(Function &F);
   bool performScalarPRE(Instruction *I);
   bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
-                                 unsigned int ValNo);
+                                 BasicBlock *Curr, unsigned int ValNo);
   Value *findLeader(const BasicBlock *BB, uint32_t num);
   void cleanupGlobalSets();
+  void fillImplicitControlFlowInfo(BasicBlock *BB);
   void verifyRemoved(const Instruction *I) const;
   bool splitCriticalEdges();
   BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
@@ -226,6 +284,7 @@ private:
   bool processFoldableCondBr(BranchInst *BI);
   void addDeadBlock(BasicBlock *BB);
   void assignValNumForDeadCode();
+  void assignBlockRPONumber(Function &F);
 };
 
 /// Create a legacy GVN pass. This also allows parameterizing whether or not
@@ -238,12 +297,14 @@ struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
   /// \brief Run the pass over the function.
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
+
 /// \brief Uses an "inverted" value numbering to decide the similarity of
 /// expressions and sinks similar expressions into successors.
 struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
   /// \brief Run the pass over the function.
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
-}
 
-#endif
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_SCALAR_GVN_H
diff --git a/include/llvm/Transforms/Scalar/GVNExpression.h b/include/llvm/Transforms/Scalar/GVNExpression.h
index f603ebcbca7cc..99dae15a3ac00 100644
--- a/include/llvm/Transforms/Scalar/GVNExpression.h
+++ b/include/llvm/Transforms/Scalar/GVNExpression.h
@@ -1,4 +1,4 @@
-//======- GVNExpression.h - GVN Expression classes --------------*- C++ -*-===//
+//===- GVNExpression.h - GVN Expression classes -----------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -6,11 +6,12 @@
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
+//
 /// \file
 ///
 /// The header file for the GVN pass that contains expression handling
 /// classes
-///
+//
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_GVNEXPRESSION_H
@@ -25,7 +26,7 @@
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/ArrayRecycler.h"
 #include "llvm/Support/Casting.h"
-#include "llvm/Support/Debug.h"
+#include "llvm/Support/Compiler.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
@@ -34,6 +35,9 @@
 
 namespace llvm {
 
+class BasicBlock;
+class Type;
+
 namespace GVNExpression {
 
 enum ExpressionType {
@@ -58,17 +62,18 @@ class Expression {
 private:
   ExpressionType EType;
   unsigned Opcode;
-  mutable hash_code HashVal;
+  mutable hash_code HashVal = 0;
 
 public:
   Expression(ExpressionType ET = ET_Base, unsigned O = ~2U)
-      : EType(ET), Opcode(O), HashVal(0) {}
+      : EType(ET), Opcode(O) {}
   Expression(const Expression &) = delete;
   Expression &operator=(const Expression &) = delete;
   virtual ~Expression();
 
   static unsigned getEmptyKey() { return ~0U; }
   static unsigned getTombstoneKey() { return ~1U; }
+
   bool operator!=(const Expression &Other) const { return !(*this == Other); }
   bool operator==(const Expression &Other) const {
     if (getOpcode() != Other.getOpcode())
@@ -83,6 +88,7 @@ public:
 
     return equals(Other);
   }
+
   hash_code getComputedHash() const {
     // It's theoretically possible for a thing to hash to zero.  In that case,
     // we will just compute the hash a few extra times, which is no worse that
@@ -93,6 +99,7 @@ public:
   }
 
   virtual bool equals(const Expression &Other) const { return true; }
+
   // Return true if the two expressions are exactly the same, including the
   // normally ignored fields.
   virtual bool exactlyEquals(const Expression &Other) const {
@@ -106,9 +113,7 @@ public:
   // We deliberately leave the expression type out of the hash value.
   virtual hash_code getHashValue() const { return getOpcode(); }
 
-  //
   // Debugging support
-  //
   virtual void printInternal(raw_ostream &OS, bool PrintEType) const {
     if (PrintEType)
       OS << "etype = " << getExpressionType() << ",";
@@ -131,19 +136,19 @@ inline raw_ostream &operator<<(raw_ostream &OS, const Expression &E) {
 
 class BasicExpression : public Expression {
 private:
-  typedef ArrayRecycler<Value *> RecyclerType;
-  typedef RecyclerType::Capacity RecyclerCapacity;
-  Value **Operands;
+  using RecyclerType = ArrayRecycler<Value *>;
+  using RecyclerCapacity = RecyclerType::Capacity;
+
+  Value **Operands = nullptr;
   unsigned MaxOperands;
-  unsigned NumOperands;
-  Type *ValueType;
+  unsigned NumOperands = 0;
+  Type *ValueType = nullptr;
 
 public:
   BasicExpression(unsigned NumOperands)
       : BasicExpression(NumOperands, ET_Basic) {}
   BasicExpression(unsigned NumOperands, ExpressionType ET)
-      : Expression(ET), Operands(nullptr), MaxOperands(NumOperands),
-        NumOperands(0), ValueType(nullptr) {}
+      : Expression(ET), MaxOperands(NumOperands) {}
   BasicExpression() = delete;
   BasicExpression(const BasicExpression &) = delete;
   BasicExpression &operator=(const BasicExpression &) = delete;
@@ -174,8 +179,9 @@ public:
 
   unsigned getNumOperands() const { return NumOperands; }
 
-  typedef Value **op_iterator;
-  typedef Value *const *const_op_iterator;
+  using op_iterator = Value **;
+  using const_op_iterator = Value *const *;
+
   op_iterator op_begin() { return Operands; }
   op_iterator op_end() { return Operands + NumOperands; }
   const_op_iterator op_begin() const { return Operands; }
@@ -219,9 +225,7 @@ public:
                         hash_combine_range(op_begin(), op_end()));
   }
 
-  //
   // Debugging support
-  //
   void printInternal(raw_ostream &OS, bool PrintEType) const override {
     if (PrintEType)
       OS << "ExpressionTypeBasic, ";
@@ -240,7 +244,8 @@ public:
 class op_inserter
     : public std::iterator<std::output_iterator_tag, void, void, void, void> {
 private:
-  typedef BasicExpression Container;
+  using Container = BasicExpression;
+
   Container *BE;
 
 public:
@@ -263,15 +268,16 @@ private:
 public:
   MemoryExpression(unsigned NumOperands, enum ExpressionType EType,
                    const MemoryAccess *MemoryLeader)
-      : BasicExpression(NumOperands, EType), MemoryLeader(MemoryLeader){};
-
+      : BasicExpression(NumOperands, EType), MemoryLeader(MemoryLeader) {}
   MemoryExpression() = delete;
   MemoryExpression(const MemoryExpression &) = delete;
   MemoryExpression &operator=(const MemoryExpression &) = delete;
+
   static bool classof(const Expression *EB) {
     return EB->getExpressionType() > ET_MemoryStart &&
            EB->getExpressionType() < ET_MemoryEnd;
   }
+
   hash_code getHashValue() const override {
     return hash_combine(this->BasicExpression::getHashValue(), MemoryLeader);
   }
@@ -305,9 +311,7 @@ public:
     return EB->getExpressionType() == ET_Call;
   }
 
-  //
   // Debugging support
-  //
   void printInternal(raw_ostream &OS, bool PrintEType) const override {
     if (PrintEType)
       OS << "ExpressionTypeCall, ";
@@ -326,11 +330,13 @@ public:
   LoadExpression(unsigned NumOperands, LoadInst *L,
                  const MemoryAccess *MemoryLeader)
       : LoadExpression(ET_Load, NumOperands, L, MemoryLeader) {}
+
   LoadExpression(enum ExpressionType EType, unsigned NumOperands, LoadInst *L,
                  const MemoryAccess *MemoryLeader)
       : MemoryExpression(NumOperands, EType, MemoryLeader), Load(L) {
     Alignment = L ? L->getAlignment() : 0;
   }
+
   LoadExpression() = delete;
   LoadExpression(const LoadExpression &) = delete;
   LoadExpression &operator=(const LoadExpression &) = delete;
@@ -352,9 +358,7 @@ public:
            cast<LoadExpression>(Other).getLoadInst() == getLoadInst();
   }
 
-  //
   // Debugging support
-  //
   void printInternal(raw_ostream &OS, bool PrintEType) const override {
     if (PrintEType)
       OS << "ExpressionTypeLoad, ";
@@ -388,13 +392,13 @@ public:
   Value *getStoredValue() const { return StoredValue; }
 
   bool equals(const Expression &Other) const override;
+
   bool exactlyEquals(const Expression &Other) const override {
     return Expression::exactlyEquals(Other) &&
            cast<StoreExpression>(Other).getStoreInst() == getStoreInst();
   }
 
   // Debugging support
-  //
   void printInternal(raw_ostream &OS, bool PrintEType) const override {
     if (PrintEType)
       OS << "ExpressionTypeStore, ";
@@ -409,14 +413,13 @@ public:
 class AggregateValueExpression final : public BasicExpression {
 private:
   unsigned MaxIntOperands;
-  unsigned NumIntOperands;
-  unsigned *IntOperands;
+  unsigned NumIntOperands = 0;
+  unsigned *IntOperands = nullptr;
 
 public:
   AggregateValueExpression(unsigned NumOperands, unsigned NumIntOperands)
       : BasicExpression(NumOperands, ET_AggregateValue),
-        MaxIntOperands(NumIntOperands), NumIntOperands(0),
-        IntOperands(nullptr) {}
+        MaxIntOperands(NumIntOperands) {}
   AggregateValueExpression() = delete;
   AggregateValueExpression(const AggregateValueExpression &) = delete;
   AggregateValueExpression &
@@ -427,8 +430,8 @@ public:
     return EB->getExpressionType() == ET_AggregateValue;
   }
 
-  typedef unsigned *int_arg_iterator;
-  typedef const unsigned *const_int_arg_iterator;
+  using int_arg_iterator = unsigned *;
+  using const_int_arg_iterator = const unsigned *;
 
   int_arg_iterator int_op_begin() { return IntOperands; }
   int_arg_iterator int_op_end() { return IntOperands + NumIntOperands; }
@@ -463,9 +466,7 @@ public:
                         hash_combine_range(int_op_begin(), int_op_end()));
   }
 
-  //
   // Debugging support
-  //
   void printInternal(raw_ostream &OS, bool PrintEType) const override {
     if (PrintEType)
       OS << "ExpressionTypeAggregateValue, ";
@@ -481,7 +482,8 @@ public:
 class int_op_inserter
     : public std::iterator<std::output_iterator_tag, void, void, void, void> {
 private:
-  typedef AggregateValueExpression Container;
+  using Container = AggregateValueExpression;
+
   Container *AVE;
 
 public:
@@ -524,9 +526,7 @@ public:
     return hash_combine(this->BasicExpression::getHashValue(), BB);
   }
 
-  //
   // Debugging support
-  //
   void printInternal(raw_ostream &OS, bool PrintEType) const override {
     if (PrintEType)
       OS << "ExpressionTypePhi, ";
@@ -573,9 +573,7 @@ public:
                         VariableValue->getType(), VariableValue);
   }
 
-  //
   // Debugging support
-  //
   void printInternal(raw_ostream &OS, bool PrintEType) const override {
     if (PrintEType)
       OS << "ExpressionTypeVariable, ";
@@ -612,9 +610,7 @@ public:
                         ConstantValue->getType(), ConstantValue);
   }
 
-  //
   // Debugging support
-  //
   void printInternal(raw_ostream &OS, bool PrintEType) const override {
     if (PrintEType)
       OS << "ExpressionTypeConstant, ";
@@ -649,9 +645,7 @@ public:
     return hash_combine(this->Expression::getHashValue(), Inst);
   }
 
-  //
   // Debugging support
-  //
   void printInternal(raw_ostream &OS, bool PrintEType) const override {
     if (PrintEType)
       OS << "ExpressionTypeUnknown, ";
diff --git a/include/llvm/Transforms/Scalar/IndVarSimplify.h b/include/llvm/Transforms/Scalar/IndVarSimplify.h
index 4a4683f1a07df..e321c8fc6e9cf 100644
--- a/include/llvm/Transforms/Scalar/IndVarSimplify.h
+++ b/include/llvm/Transforms/Scalar/IndVarSimplify.h
@@ -15,17 +15,20 @@
 #ifndef LLVM_TRANSFORMS_SCALAR_INDVARSIMPLIFY_H
 #define LLVM_TRANSFORMS_SCALAR_INDVARSIMPLIFY_H
 
-#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/IR/PassManager.h"
-#include "llvm/Transforms/Scalar/LoopPassManager.h"
 
 namespace llvm {
 
+class Loop;
+class LPMUpdater;
+
 class IndVarSimplifyPass : public PassInfoMixin<IndVarSimplifyPass> {
 public:
   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
                         LoopStandardAnalysisResults &AR, LPMUpdater &U);
 };
-}
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_INDVARSIMPLIFY_H
diff --git a/include/llvm/Transforms/Scalar/JumpThreading.h b/include/llvm/Transforms/Scalar/JumpThreading.h
index 1da86132591b7..a9466713b8e65 100644
--- a/include/llvm/Transforms/Scalar/JumpThreading.h
+++ b/include/llvm/Transforms/Scalar/JumpThreading.h
@@ -6,41 +6,57 @@
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
+//
 /// \file
 /// See the comments on JumpThreadingPass.
-///
+//
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
 #define LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
 
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
-#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
-#include "llvm/Analysis/LazyValueInfo.h"
-#include "llvm/Analysis/TargetLibraryInfo.h"
-#include "llvm/IR/Instructions.h"
-#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/ValueHandle.h"
+#include <memory>
+#include <utility>
 
 namespace llvm {
 
+class BasicBlock;
+class BinaryOperator;
+class BranchInst;
+class CmpInst;
+class Constant;
+class Function;
+class Instruction;
+class IntrinsicInst;
+class LazyValueInfo;
+class LoadInst;
+class PHINode;
+class TargetLibraryInfo;
+class Value;
+
 /// A private "module" namespace for types and utilities used by
 /// JumpThreading.
 /// These are implementation details and should not be used by clients.
 namespace jumpthreading {
+
 // These are at global scope so static functions can use them too.
-typedef SmallVectorImpl<std::pair<Constant *, BasicBlock *>> PredValueInfo;
-typedef SmallVector<std::pair<Constant *, BasicBlock *>, 8> PredValueInfoTy;
+using PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>;
+using PredValueInfoTy = SmallVector<std::pair<Constant *, BasicBlock *>, 8>;
 
 // This is used to keep track of what kind of constant we're currently hoping
 // to find.
 enum ConstantPreference { WantInteger, WantBlockAddress };
-}
+
+} // end namespace jumpthreading
 
 /// This pass performs 'jump threading', which looks at blocks that have
 /// multiple predecessors and multiple successors.  If one or more of the
@@ -57,7 +73,6 @@ enum ConstantPreference { WantInteger, WantBlockAddress };
 ///
 /// In this case, the unconditional branch at the end of the first if can be
 /// revectored to the false side of the second if.
-///
 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
   TargetLibraryInfo *TLI;
   LazyValueInfo *LVI;
@@ -141,4 +156,4 @@ private:
 
 } // end namespace llvm
 
-#endif
+#endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
diff --git a/include/llvm/Transforms/Scalar/LoopDistribute.h b/include/llvm/Transforms/Scalar/LoopDistribute.h
index ddde5954c2189..2bf1c9d696d5b 100644
--- a/include/llvm/Transforms/Scalar/LoopDistribute.h
+++ b/include/llvm/Transforms/Scalar/LoopDistribute.h
@@ -21,10 +21,13 @@
 
 namespace llvm {
 
+class Function;
+
 class LoopDistributePass : public PassInfoMixin<LoopDistributePass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_LOOPDISTRIBUTE_H
diff --git a/include/llvm/Transforms/Scalar/LoopIdiomRecognize.h b/include/llvm/Transforms/Scalar/LoopIdiomRecognize.h
index 40349e8f7fe06..7added8d2c617 100644
--- a/include/llvm/Transforms/Scalar/LoopIdiomRecognize.h
+++ b/include/llvm/Transforms/Scalar/LoopIdiomRecognize.h
@@ -1,4 +1,4 @@
-//===- LoopIdiomRecognize.h - Loop Idiom Recognize Pass -------*- C++ -*-===//
+//===- LoopIdiomRecognize.h - Loop Idiom Recognize Pass ---------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -16,18 +16,21 @@
 #ifndef LLVM_TRANSFORMS_SCALAR_LOOPIDIOMRECOGNIZE_H
 #define LLVM_TRANSFORMS_SCALAR_LOOPIDIOMRECOGNIZE_H
 
-#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/IR/PassManager.h"
-#include "llvm/Transforms/Scalar/LoopPassManager.h"
 
 namespace llvm {
 
+class Loop;
+class LPMUpdater;
+
 /// Performs Loop Idiom Recognize Pass.
 class LoopIdiomRecognizePass : public PassInfoMixin<LoopIdiomRecognizePass> {
 public:
   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
                         LoopStandardAnalysisResults &AR, LPMUpdater &U);
 };
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_LOOPIDIOMRECOGNIZE_H
diff --git a/include/llvm/Transforms/Scalar/LoopInstSimplify.h b/include/llvm/Transforms/Scalar/LoopInstSimplify.h
index bb8bc29577a2d..04dc79c3fa573 100644
--- a/include/llvm/Transforms/Scalar/LoopInstSimplify.h
+++ b/include/llvm/Transforms/Scalar/LoopInstSimplify.h
@@ -1,4 +1,4 @@
-//===- LoopInstSimplify.h - Loop Inst Simplify Pass -------*- C++ -*-===//
+//===- LoopInstSimplify.h - Loop Inst Simplify Pass -------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -14,18 +14,21 @@
 #ifndef LLVM_TRANSFORMS_SCALAR_LOOPINSTSIMPLIFY_H
 #define LLVM_TRANSFORMS_SCALAR_LOOPINSTSIMPLIFY_H
 
-#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/IR/PassManager.h"
-#include "llvm/Transforms/Scalar/LoopPassManager.h"
 
 namespace llvm {
 
+class Loop;
+class LPMUpdater;
+
 /// Performs Loop Inst Simplify Pass.
 class LoopInstSimplifyPass : public PassInfoMixin<LoopInstSimplifyPass> {
 public:
   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
                         LoopStandardAnalysisResults &AR, LPMUpdater &U);
 };
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_LOOPINSTSIMPLIFY_H
diff --git a/include/llvm/Transforms/Scalar/LoopLoadElimination.h b/include/llvm/Transforms/Scalar/LoopLoadElimination.h
index 7a007a7e822d2..b0514a4a7c989 100644
--- a/include/llvm/Transforms/Scalar/LoopLoadElimination.h
+++ b/include/llvm/Transforms/Scalar/LoopLoadElimination.h
@@ -1,4 +1,4 @@
-//===---- LoopLoadElimination.h ---------------------------------*- C++ -*-===//
+//===- LoopLoadElimination.h ------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -6,11 +6,12 @@
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
+//
 /// \file
 /// This header defines the LoopLoadEliminationPass object. This pass forwards
 /// loaded values around loop backedges to allow their use in subsequent
 /// iterations.
-///
+//
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_LOOPLOADELIMINATION_H
@@ -20,11 +21,14 @@
 
 namespace llvm {
 
+class Function;
+
 /// Pass to forward loads in a loop around the backedge to subsequent
 /// iterations.
 struct LoopLoadEliminationPass : public PassInfoMixin<LoopLoadEliminationPass> {
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
-}
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_LOOPLOADELIMINATION_H
diff --git a/include/llvm/Transforms/Scalar/LoopPassManager.h b/include/llvm/Transforms/Scalar/LoopPassManager.h
index 715b11d3d9749..473b97dc7e8d4 100644
--- a/include/llvm/Transforms/Scalar/LoopPassManager.h
+++ b/include/llvm/Transforms/Scalar/LoopPassManager.h
@@ -164,10 +164,11 @@ public:
   /// If this is called for the current loop, in addition to clearing any
   /// state, this routine will mark that the current loop should be skipped by
   /// the rest of the pass management infrastructure.
-  void markLoopAsDeleted(Loop &L) {
-    LAM.clear(L);
-    assert(CurrentL->contains(&L) && "Cannot delete a loop outside of the "
-                                     "subloop tree currently being processed.");
+  void markLoopAsDeleted(Loop &L, llvm::StringRef Name) {
+    LAM.clear(L, Name);
+    assert((&L == CurrentL || CurrentL->contains(&L)) &&
+           "Cannot delete a loop outside of the "
+           "subloop tree currently being processed.");
     if (&L == CurrentL)
       SkipCurrentLoop = true;
   }
@@ -216,6 +217,19 @@ public:
     // shouldn't impact anything.
   }
 
+  /// Restart the current loop.
+  ///
+  /// Loop passes should call this method to indicate the current loop has been
+  /// sufficiently changed that it should be re-visited from the begining of
+  /// the loop pass pipeline rather than continuing.
+  void revisitCurrentLoop() {
+    // Tell the currently in-flight pipeline to stop running.
+    SkipCurrentLoop = true;
+
+    // And insert ourselves back into the worklist.
+    Worklist.insert(CurrentL);
+  }
+
 private:
   template <typename LoopPassT> friend class llvm::FunctionToLoopPassAdaptor;
 
@@ -271,13 +285,17 @@ public:
       return PA;
 
     // Get the analysis results needed by loop passes.
+    MemorySSA *MSSA = EnableMSSALoopDependency
+                          ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA())
+                          : nullptr;
     LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
                                        AM.getResult<AssumptionAnalysis>(F),
                                        AM.getResult<DominatorTreeAnalysis>(F),
                                        AM.getResult<LoopAnalysis>(F),
                                        AM.getResult<ScalarEvolutionAnalysis>(F),
                                        AM.getResult<TargetLibraryAnalysis>(F),
-                                       AM.getResult<TargetIRAnalysis>(F)};
+                                       AM.getResult<TargetIRAnalysis>(F),
+                                       MSSA};
 
     // Setup the loop analysis manager from its proxy. It is important that
     // this is only done when there are loops to process and we have built the
@@ -345,6 +363,8 @@ public:
     PA.preserve<DominatorTreeAnalysis>();
     PA.preserve<LoopAnalysis>();
     PA.preserve<ScalarEvolutionAnalysis>();
+    // FIXME: Uncomment this when all loop passes preserve MemorySSA
+    // PA.preserve<MemorySSAAnalysis>();
     // FIXME: What we really want to do here is preserve an AA category, but
     // that concept doesn't exist yet.
     PA.preserve<AAManager>();
diff --git a/include/llvm/Transforms/Scalar/LoopStrengthReduce.h b/include/llvm/Transforms/Scalar/LoopStrengthReduce.h
index ebcb32125262b..62c038a3857d6 100644
--- a/include/llvm/Transforms/Scalar/LoopStrengthReduce.h
+++ b/include/llvm/Transforms/Scalar/LoopStrengthReduce.h
@@ -1,4 +1,4 @@
-//===- LoopStrengthReduce.h - Loop Strength Reduce Pass -------*- C++ -*-===//
+//===- LoopStrengthReduce.h - Loop Strength Reduce Pass ---------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -22,18 +22,21 @@
 #ifndef LLVM_TRANSFORMS_SCALAR_LOOPSTRENGTHREDUCE_H
 #define LLVM_TRANSFORMS_SCALAR_LOOPSTRENGTHREDUCE_H
 
-#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/IR/PassManager.h"
-#include "llvm/Transforms/Scalar/LoopPassManager.h"
 
 namespace llvm {
 
+class Loop;
+class LPMUpdater;
+
 /// Performs Loop Strength Reduce Pass.
 class LoopStrengthReducePass : public PassInfoMixin<LoopStrengthReducePass> {
 public:
   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
                         LoopStandardAnalysisResults &AR, LPMUpdater &U);
 };
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_LOOPSTRENGTHREDUCE_H
diff --git a/include/llvm/Transforms/Scalar/LoopUnrollPass.h b/include/llvm/Transforms/Scalar/LoopUnrollPass.h
index 7253bd09766ef..9848e0d54f2bf 100644
--- a/include/llvm/Transforms/Scalar/LoopUnrollPass.h
+++ b/include/llvm/Transforms/Scalar/LoopUnrollPass.h
@@ -10,40 +10,40 @@
 #ifndef LLVM_TRANSFORMS_SCALAR_LOOPUNROLLPASS_H
 #define LLVM_TRANSFORMS_SCALAR_LOOPUNROLLPASS_H
 
-#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/IR/PassManager.h"
-#include "llvm/Transforms/Scalar/LoopPassManager.h"
 
 namespace llvm {
 
-class LoopUnrollPass : public PassInfoMixin<LoopUnrollPass> {
-  const bool AllowPartialUnrolling;
+class Function;
+class Loop;
+class LPMUpdater;
+
+/// Loop unroll pass that only does full loop unrolling.
+class LoopFullUnrollPass : public PassInfoMixin<LoopFullUnrollPass> {
   const int OptLevel;
 
-  explicit LoopUnrollPass(bool AllowPartialUnrolling, int OptLevel)
-      : AllowPartialUnrolling(AllowPartialUnrolling), OptLevel(OptLevel) {}
+public:
+  explicit LoopFullUnrollPass(int OptLevel = 2) : OptLevel(OptLevel) {}
+
+  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
+                        LoopStandardAnalysisResults &AR, LPMUpdater &U);
+};
+
+/// Loop unroll pass that will support both full and partial unrolling.
+/// It is a function pass to have access to function and module analyses.
+/// It will also put loops into canonical form (simplified and LCSSA).
+class LoopUnrollPass : public PassInfoMixin<LoopUnrollPass> {
+  const int OptLevel;
 
 public:
-  /// Create an instance of the loop unroll pass that will support both full
-  /// and partial unrolling.
-  ///
   /// This uses the target information (or flags) to control the thresholds for
   /// different unrolling stategies but supports all of them.
-  static LoopUnrollPass create(int OptLevel = 2) {
-    return LoopUnrollPass(/*AllowPartialUnrolling*/ true, OptLevel);
-  }
-
-  /// Create an instance of the loop unroll pass that only does full loop
-  /// unrolling.
-  ///
-  /// This will disable any runtime or partial unrolling.
-  static LoopUnrollPass createFull(int OptLevel = 2) {
-    return LoopUnrollPass(/*AllowPartialUnrolling*/ false, OptLevel);
-  }
+  explicit LoopUnrollPass(int OptLevel = 2) : OptLevel(OptLevel) {}
 
-  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
-                        LoopStandardAnalysisResults &AR, LPMUpdater &U);
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_LOOPUNROLLPASS_H
diff --git a/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h b/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h
index f688e7f19986c..ab9dec0311b2b 100644
--- a/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h
+++ b/include/llvm/Transforms/Scalar/LowerExpectIntrinsic.h
@@ -24,7 +24,7 @@ namespace llvm {
 struct LowerExpectIntrinsicPass : PassInfoMixin<LowerExpectIntrinsicPass> {
   /// \brief Run the pass over the function.
   ///
-  /// This will lower all of th expect intrinsic calls in this function into
+  /// This will lower all of the expect intrinsic calls in this function into
   /// branch weight metadata. That metadata will subsequently feed the analysis
   /// of the probabilities and frequencies of the CFG. After running this pass,
   /// no more expect intrinsics remain, allowing the rest of the optimizer to
diff --git a/include/llvm/Transforms/Scalar/MemCpyOptimizer.h b/include/llvm/Transforms/Scalar/MemCpyOptimizer.h
index f52872dd2ea78..046c808bd0511 100644
--- a/include/llvm/Transforms/Scalar/MemCpyOptimizer.h
+++ b/include/llvm/Transforms/Scalar/MemCpyOptimizer.h
@@ -1,4 +1,4 @@
-//===---- MemCpyOptimizer.h - memcpy optimization ---------------*- C++ -*-===//
+//===- MemCpyOptimizer.h - memcpy optimization ------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -16,20 +16,27 @@
 #define LLVM_TRANSFORMS_SCALAR_MEMCPYOPTIMIZER_H
 
 #include "llvm/Analysis/AliasAnalysis.h"
-#include "llvm/Analysis/AssumptionCache.h"
-#include "llvm/Analysis/MemoryDependenceAnalysis.h"
-#include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/Dominators.h"
-#include "llvm/IR/Function.h"
-#include "llvm/IR/Instructions.h"
-#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/CallSite.h"
 #include "llvm/IR/PassManager.h"
 #include <cstdint>
 #include <functional>
 
 namespace llvm {
 
+class AssumptionCache;
+class CallInst;
+class DominatorTree;
+class Function;
+class Instruction;
+class MemCpyInst;
+class MemMoveInst;
+class MemoryDependenceResults;
+class MemSetInst;
+class StoreInst;
+class TargetLibraryInfo;
+class Value;
+
 class MemCpyOptPass : public PassInfoMixin<MemCpyOptPass> {
   MemoryDependenceResults *MD = nullptr;
   TargetLibraryInfo *TLI = nullptr;
@@ -41,6 +48,7 @@ public:
   MemCpyOptPass() = default;
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+
   // Glue for the old PM.
   bool runImpl(Function &F, MemoryDependenceResults *MD_,
                TargetLibraryInfo *TLI_,
diff --git a/include/llvm/Transforms/Scalar/NaryReassociate.h b/include/llvm/Transforms/Scalar/NaryReassociate.h
index f35707eeb3f04..e835bd5f0761c 100644
--- a/include/llvm/Transforms/Scalar/NaryReassociate.h
+++ b/include/llvm/Transforms/Scalar/NaryReassociate.h
@@ -1,4 +1,4 @@
-//===- NaryReassociate.h - Reassociate n-ary expressions ------------------===//
+//===- NaryReassociate.h - Reassociate n-ary expressions --------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -81,15 +81,25 @@
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
-#include "llvm/Analysis/AssumptionCache.h"
-#include "llvm/Analysis/ScalarEvolution.h"
-#include "llvm/Analysis/TargetLibraryInfo.h"
-#include "llvm/Analysis/TargetTransformInfo.h"
-#include "llvm/IR/Dominators.h"
-#include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/ValueHandle.h"
 
 namespace llvm {
+
+class AssumptionCache;
+class BinaryOperator;
+class DataLayout;
+class DominatorTree;
+class Function;
+class GetElementPtrInst;
+class Instruction;
+class ScalarEvolution;
+class SCEV;
+class TargetLibraryInfo;
+class TargetTransformInfo;
+class Type;
+class Value;
+
 class NaryReassociatePass : public PassInfoMixin<NaryReassociatePass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
@@ -109,6 +119,7 @@ private:
 
   // Reassociate GEP for better CSE.
   Instruction *tryReassociateGEP(GetElementPtrInst *GEP);
+
   // Try splitting GEP at the I-th index and see whether either part can be
   // CSE'ed. This is a helper function for tryReassociateGEP.
   //
@@ -118,6 +129,7 @@ private:
   //                                      ..., i-th index).
   GetElementPtrInst *tryReassociateGEPAtIndex(GetElementPtrInst *GEP,
                                               unsigned I, Type *IndexedType);
+
   // Given GEP's I-th index = LHS + RHS, see whether &Base[..][LHS][..] or
   // &Base[..][RHS][..] can be CSE'ed and rewrite GEP accordingly.
   GetElementPtrInst *tryReassociateGEPAtIndex(GetElementPtrInst *GEP,
@@ -146,6 +158,7 @@ private:
   // \c CandidateExpr. Returns null if not found.
   Instruction *findClosestMatchingDominator(const SCEV *CandidateExpr,
                                             Instruction *Dominatee);
+
   // GetElementPtrInst implicitly sign-extends an index if the index is shorter
   // than the pointer size. This function returns whether Index is shorter than
   // GEP's pointer size, i.e., whether Index needs to be sign-extended in order
@@ -158,6 +171,7 @@ private:
   ScalarEvolution *SE;
   TargetLibraryInfo *TLI;
   TargetTransformInfo *TTI;
+
   // A lookup table quickly telling which instructions compute the given SCEV.
   // Note that there can be multiple instructions at different locations
   // computing to the same SCEV, so we map a SCEV to an instruction list.  For
@@ -169,6 +183,7 @@ private:
   //     bar(a + b);
   DenseMap<const SCEV *, SmallVector<WeakTrackingVH, 2>> SeenExprs;
 };
-} // namespace llvm
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H
diff --git a/include/llvm/Transforms/Scalar/NewGVN.h b/include/llvm/Transforms/Scalar/NewGVN.h
index d0425aa4345ff..05db25502dc3c 100644
--- a/include/llvm/Transforms/Scalar/NewGVN.h
+++ b/include/llvm/Transforms/Scalar/NewGVN.h
@@ -1,4 +1,4 @@
-//===----- NewGVN.h - Global Value Numbering Pass ---------------*- C++ -*-===//
+//===- NewGVN.h - Global Value Numbering Pass -------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -6,9 +6,10 @@
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
+//
 /// \file
 /// This file provides the interface for LLVM's Global Value Numbering pass.
-///
+//
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_NEWGVN_H
@@ -17,12 +18,16 @@
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
+
+class Function;
+
 class NewGVNPass : public PassInfoMixin<NewGVNPass> {
 public:
   /// \brief Run the pass over the function.
   PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM);
 };
-}
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_NEWGVN_H
 
diff --git a/include/llvm/Transforms/Scalar/Reassociate.h b/include/llvm/Transforms/Scalar/Reassociate.h
index a30a7176baa8b..9997dfa5b6f3a 100644
--- a/include/llvm/Transforms/Scalar/Reassociate.h
+++ b/include/llvm/Transforms/Scalar/Reassociate.h
@@ -23,22 +23,33 @@
 #ifndef LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
 #define LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/IR/IRBuilder.h"
-#include "llvm/IR/Operator.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/ValueHandle.h"
 
 namespace llvm {
 
+class APInt;
+class BasicBlock;
+class BinaryOperator;
+class Function;
+class Instruction;
+class Value;
+
 /// A private "module" namespace for types and utilities used by Reassociate.
 /// These are implementation details and should not be used by clients.
 namespace reassociate {
+
 struct ValueEntry {
   unsigned Rank;
   Value *Op;
+
   ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {}
 };
+
 inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) {
   return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start.
 }
@@ -48,17 +59,26 @@ inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) {
 struct Factor {
   Value *Base;
   unsigned Power;
+
   Factor(Value *Base, unsigned Power) : Base(Base), Power(Power) {}
 };
 
 class XorOpnd;
-}
+
+} // end namespace reassociate
 
 /// Reassociate commutative expressions.
 class ReassociatePass : public PassInfoMixin<ReassociatePass> {
   DenseMap<BasicBlock *, unsigned> RankMap;
   DenseMap<AssertingVH<Value>, unsigned> ValueRankMap;
   SetVector<AssertingVH<Instruction>> RedoInsts;
+
+  // Arbitrary, but prevents quadratic behavior.
+  static const unsigned GlobalReassociateLimit = 10;
+  static const unsigned NumBinaryOps =
+      Instruction::BinaryOpsEnd - Instruction::BinaryOpsBegin;
+  DenseMap<std::pair<Value *, Value *>, unsigned> PairMap[NumBinaryOps];
+
   bool MadeChange;
 
 public:
@@ -92,7 +112,9 @@ private:
                                  SetVector<AssertingVH<Instruction>> &Insts);
   void OptimizeInst(Instruction *I);
   Instruction *canonicalizeNegConstExpr(Instruction *I);
+  void BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT);
 };
-}
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
diff --git a/include/llvm/Transforms/Scalar/RewriteStatepointsForGC.h b/include/llvm/Transforms/Scalar/RewriteStatepointsForGC.h
new file mode 100644
index 0000000000000..128f176f44203
--- /dev/null
+++ b/include/llvm/Transforms/Scalar/RewriteStatepointsForGC.h
@@ -0,0 +1,39 @@
+//===- RewriteStatepointsForGC.h - ------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides interface to "Rewrite Statepoints for GC" pass.
+//
+// This passe rewrites call/invoke instructions so as to make potential
+// relocations performed by the garbage collector explicit in the IR.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_REWRITE_STATEPOINTS_FOR_GC_H
+#define LLVM_TRANSFORMS_SCALAR_REWRITE_STATEPOINTS_FOR_GC_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+class DominatorTree;
+class Function;
+class Module;
+class TargetTransformInfo;
+class TargetLibraryInfo;
+
+struct RewriteStatepointsForGC : public PassInfoMixin<RewriteStatepointsForGC> {
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
+
+  bool runOnFunction(Function &F, DominatorTree &, TargetTransformInfo &,
+                     const TargetLibraryInfo &);
+};
+
+} // namespace llvm
+
+#endif // LLVM_TRANSFORMS_SCALAR_REWRITE_STATEPOINTS_FOR_GC_H
diff --git a/include/llvm/Transforms/Scalar/SCCP.h b/include/llvm/Transforms/Scalar/SCCP.h
index 6e7f77fe2c501..b93287fff907a 100644
--- a/include/llvm/Transforms/Scalar/SCCP.h
+++ b/include/llvm/Transforms/Scalar/SCCP.h
@@ -6,7 +6,8 @@
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
-/// \file
+//
+// \file
 // This file implements sparse conditional constant propagation and merging:
 //
 // Specifically, this:
@@ -15,22 +16,23 @@
 //   * Proves values to be constant, and replaces them with constants
 //   * Proves conditional branches to be unconditional
 //
-///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_SCCP_H
 #define LLVM_TRANSFORMS_SCALAR_SCCP_H
 
-#include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
+class Function;
+
 /// This pass performs function-level constant propagation and merging.
 class SCCPPass : public PassInfoMixin<SCCPPass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
-}
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_SCCP_H
diff --git a/include/llvm/Transforms/Scalar/SROA.h b/include/llvm/Transforms/Scalar/SROA.h
index 3080b75ba8949..4a321e75c68b8 100644
--- a/include/llvm/Transforms/Scalar/SROA.h
+++ b/include/llvm/Transforms/Scalar/SROA.h
@@ -17,15 +17,23 @@
 #define LLVM_TRANSFORMS_SCALAR_SROA_H
 
 #include "llvm/ADT/SetVector.h"
-#include "llvm/Analysis/AssumptionCache.h"
-#include "llvm/IR/Dominators.h"
-#include "llvm/IR/Function.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Compiler.h"
 #include <vector>
 
 namespace llvm {
 
+class AllocaInst;
+class AssumptionCache;
+class DominatorTree;
+class Function;
+class Instruction;
+class LLVMContext;
+class PHINode;
+class SelectInst;
+class Use;
+
 /// A private "module" namespace for types and utilities used by SROA. These
 /// are implementation details and should not be used by clients.
 namespace sroa LLVM_LIBRARY_VISIBILITY {
@@ -122,7 +130,7 @@ private:
   bool splitAlloca(AllocaInst &AI, sroa::AllocaSlices &AS);
   bool runOnAlloca(AllocaInst &AI);
   void clobberUse(Use &U);
-  void deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas);
+  bool deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas);
   bool promoteAllocas(Function &F);
 };
 
diff --git a/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h b/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h
index d7282ac6a7813..63bfe6373d04f 100644
--- a/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h
+++ b/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h
@@ -36,8 +36,10 @@ namespace llvm {
 /// of the loop, to make the unswitching opportunity obvious.
 ///
 class SimpleLoopUnswitchPass : public PassInfoMixin<SimpleLoopUnswitchPass> {
+  bool NonTrivial;
+
 public:
-  SimpleLoopUnswitchPass() = default;
+  SimpleLoopUnswitchPass(bool NonTrivial = false) : NonTrivial(NonTrivial) {}
 
   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
                         LoopStandardAnalysisResults &AR, LPMUpdater &U);
@@ -46,7 +48,7 @@ public:
 /// Create the legacy pass object for the simple loop unswitcher.
 ///
 /// See the documentaion for `SimpleLoopUnswitchPass` for details.
-Pass *createSimpleLoopUnswitchLegacyPass();
+Pass *createSimpleLoopUnswitchLegacyPass(bool NonTrivial = false);
 
 } // end namespace llvm
 
diff --git a/include/llvm/Transforms/Scalar/SimplifyCFG.h b/include/llvm/Transforms/Scalar/SimplifyCFG.h
index 54b51c405ad41..1afb9c7f954f4 100644
--- a/include/llvm/Transforms/Scalar/SimplifyCFG.h
+++ b/include/llvm/Transforms/Scalar/SimplifyCFG.h
@@ -17,26 +17,34 @@
 
 #include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/Transforms/Utils/Local.h"
 
 namespace llvm {
 
-/// \brief A pass to simplify and canonicalize the CFG of a function.
+/// A pass to simplify and canonicalize the CFG of a function.
 ///
-/// This pass iteratively simplifies the entire CFG of a function, removing
-/// unnecessary control flows and bringing it into the canonical form expected
-/// by the rest of the mid-level optimizer.
+/// This pass iteratively simplifies the entire CFG of a function. It may change
+/// or remove control flow to put the CFG into a canonical form expected by
+/// other passes of the mid-level optimizer. Depending on the specified options,
+/// it may further optimize control-flow to create non-canonical forms.
 class SimplifyCFGPass : public PassInfoMixin<SimplifyCFGPass> {
-  int BonusInstThreshold;
-  bool LateSimplifyCFG;
+  SimplifyCFGOptions Options;
 
 public:
-  /// \brief Construct a pass with the default thresholds
-  /// and switch optimizations.
-  SimplifyCFGPass();
-
-  /// \brief Construct a pass with a specific bonus threshold
-  /// and optional switch optimizations.
-  SimplifyCFGPass(int BonusInstThreshold, bool LateSimplifyCFG);
+  /// The default constructor sets the pass options to create canonical IR,
+  /// rather than optimal IR. That is, by default we bypass transformations that
+  /// are likely to improve performance but make analysis for other passes more
+  /// difficult.
+  SimplifyCFGPass()
+      : SimplifyCFGPass(SimplifyCFGOptions()
+                            .forwardSwitchCondToPhi(false)
+                            .convertSwitchToLookupTable(false)
+                            .needCanonicalLoops(true)
+                            .sinkCommonInsts(false)) {}
+
+
+  /// Construct a pass with optional optimizations.
+  SimplifyCFGPass(const SimplifyCFGOptions &PassOptions);
 
   /// \brief Run the pass over the function.
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
diff --git a/include/llvm/Transforms/Scalar/SpeculateAroundPHIs.h b/include/llvm/Transforms/Scalar/SpeculateAroundPHIs.h
new file mode 100644
index 0000000000000..f39e03d22d656
--- /dev/null
+++ b/include/llvm/Transforms/Scalar/SpeculateAroundPHIs.h
@@ -0,0 +1,111 @@
+//===- SpeculateAroundPHIs.h - Speculate around PHIs ------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_SPECULATEAROUNDPHIS_H
+#define LLVM_TRANSFORMS_SCALAR_SPECULATEAROUNDPHIS_H
+
+#include "llvm/ADT/SetVector.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Support/Compiler.h"
+#include <vector>
+
+namespace llvm {
+
+/// This pass handles simple speculating of  instructions around PHIs when
+/// doing so is profitable for a particular target despite duplicated
+/// instructions.
+///
+/// The motivating example are PHIs of constants which will require
+/// materializing the constants along each edge. If the PHI is used by an
+/// instruction where the target can materialize the constant as part of the
+/// instruction, it is profitable to speculate those instructions around the
+/// PHI node. This can reduce dynamic instruction count as well as decrease
+/// register pressure.
+///
+/// Consider this IR for example:
+///   ```
+///   entry:
+///     br i1 %flag, label %a, label %b
+///
+///   a:
+///     br label %exit
+///
+///   b:
+///     br label %exit
+///
+///   exit:
+///     %p = phi i32 [ 7, %a ], [ 11, %b ]
+///     %sum = add i32 %arg, %p
+///     ret i32 %sum
+///   ```
+/// To materialize the inputs to this PHI node may require an explicit
+/// instruction. For example, on x86 this would turn into something like
+///   ```
+///     testq %eax, %eax
+///     movl $7, %rNN
+///     jne .L
+///     movl $11, %rNN
+///   .L:
+///     addl %edi, %rNN
+///     movl %rNN, %eax
+///     retq
+///   ```
+/// When these constants can be folded directly into another instruction, it
+/// would be preferable to avoid the potential for register pressure (above we
+/// can easily avoid it, but that isn't always true) and simply duplicate the
+/// instruction using the PHI:
+///   ```
+///   entry:
+///     br i1 %flag, label %a, label %b
+///
+///   a:
+///     %sum.1 = add i32 %arg, 7
+///     br label %exit
+///
+///   b:
+///     %sum.2 = add i32 %arg, 11
+///     br label %exit
+///
+///   exit:
+///     %p = phi i32 [ %sum.1, %a ], [ %sum.2, %b ]
+///     ret i32 %p
+///   ```
+/// Which will generate something like the following on x86:
+///   ```
+///     testq %eax, %eax
+///     addl $7, %edi
+///     jne .L
+///     addl $11, %edi
+///   .L:
+///     movl %edi, %eax
+///     retq
+///   ```
+///
+/// It is important to note that this pass is never intended to handle more
+/// complex cases where speculating around PHIs allows simplifications of the
+/// IR itself or other subsequent optimizations. Those can and should already
+/// be handled before this pass is ever run by a more powerful analysis that
+/// can reason about equivalences and common subexpressions. Classically, those
+/// cases would be handled by a GVN-powered PRE or similar transform. This
+/// pass, in contrast, is *only* interested in cases where despite no
+/// simplifications to the IR itself, speculation is *faster* to execute. The
+/// result of this is that the cost models which are appropriate to consider
+/// here are relatively simple ones around execution and codesize cost, without
+/// any need to consider simplifications or other transformations.
+struct SpeculateAroundPHIsPass : PassInfoMixin<SpeculateAroundPHIsPass> {
+  /// \brief Run the pass over the function.
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_SCALAR_SPECULATEAROUNDPHIS_H
diff --git a/include/llvm/Transforms/Utils/AddDiscriminators.h b/include/llvm/Transforms/Utils/AddDiscriminators.h
index a877583009922..4dad06e6c1254 100644
--- a/include/llvm/Transforms/Utils/AddDiscriminators.h
+++ b/include/llvm/Transforms/Utils/AddDiscriminators.h
@@ -1,4 +1,4 @@
-//===- AddDiscriminators.h -------------------------------------*- C++ -*-===//
+//===- AddDiscriminators.h --------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -20,10 +20,13 @@
 
 namespace llvm {
 
+class Function;
+
 class AddDiscriminatorsPass : public PassInfoMixin<AddDiscriminatorsPass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_ADDDISCRIMINATORS_H
diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h
index 85bb053135a65..74f75509f550e 100644
--- a/include/llvm/Transforms/Utils/BasicBlockUtils.h
+++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h
@@ -1,4 +1,4 @@
-//===-- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils ----*- C++ -*-===//
+//===- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils -----*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -25,13 +25,17 @@
 
 namespace llvm {
 
-class MemoryDependenceResults;
+class BlockFrequencyInfo;
+class BranchProbabilityInfo;
 class DominatorTree;
-class LoopInfo;
+class Function;
 class Instruction;
+class LoopInfo;
 class MDNode;
+class MemoryDependenceResults;
 class ReturnInst;
 class TargetLibraryInfo;
+class Value;
 
 /// Delete the specified block, which must have no predecessors.
 void DeleteDeadBlock(BasicBlock *BB);
@@ -118,7 +122,6 @@ struct CriticalEdgeSplittingOptions {
 /// IndirectBrInst.  Splitting these edges will almost always create an invalid
 /// program because the address of the new block won't be the one that is jumped
 /// to.
-///
 BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
                               const CriticalEdgeSplittingOptions &Options =
                                   CriticalEdgeSplittingOptions());
@@ -194,7 +197,6 @@ BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt,
 /// no other analyses. In particular, it does not preserve LoopSimplify
 /// (because it's complicated to handle the case where one of the edges being
 /// split is an exit of a loop with other exits).
-///
 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
                                    const char *Suffix,
                                    DominatorTree *DT = nullptr,
@@ -212,7 +214,6 @@ BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
 /// no other analyses. In particular, it does not preserve LoopSimplify
 /// (because it's complicated to handle the case where one of the edges being
 /// split is an exit of a loop with other exits).
-///
 void SplitLandingPadPredecessors(BasicBlock *OrigBB,
                                  ArrayRef<BasicBlock *> Preds,
                                  const char *Suffix, const char *Suffix2,
@@ -284,6 +285,29 @@ void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
 Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,
                       BasicBlock *&IfFalse);
 
+// Split critical edges where the source of the edge is an indirectbr
+// instruction. This isn't always possible, but we can handle some easy cases.
+// This is useful because MI is unable to split such critical edges,
+// which means it will not be able to sink instructions along those edges.
+// This is especially painful for indirect branches with many successors, where
+// we end up having to prepare all outgoing values in the origin block.
+//
+// Our normal algorithm for splitting critical edges requires us to update
+// the outgoing edges of the edge origin block, but for an indirectbr this
+// is hard, since it would require finding and updating the block addresses
+// the indirect branch uses. But if a block only has a single indirectbr
+// predecessor, with the others being regular branches, we can do it in a
+// different way.
+// Say we have A -> D, B -> D, I -> D where only I -> D is an indirectbr.
+// We can split D into D0 and D1, where D0 contains only the PHIs from D,
+// and D1 is the D block body. We can then duplicate D0 as D0A and D0B, and
+// create the following structure:
+// A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1
+// If BPI and BFI aren't non-null, BPI/BFI will be updated accordingly.
+bool SplitIndirectBrCriticalEdges(Function &F,
+                                  BranchProbabilityInfo *BPI = nullptr,
+                                  BlockFrequencyInfo *BFI = nullptr);
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
diff --git a/include/llvm/Transforms/Utils/BypassSlowDivision.h b/include/llvm/Transforms/Utils/BypassSlowDivision.h
index af0d60b2625f7..6eca5ed2154e2 100644
--- a/include/llvm/Transforms/Utils/BypassSlowDivision.h
+++ b/include/llvm/Transforms/Utils/BypassSlowDivision.h
@@ -1,4 +1,4 @@
-//===- llvm/Transforms/Utils/BypassSlowDivision.h --------------*- C++ -*-===//
+//===- llvm/Transforms/Utils/BypassSlowDivision.h ---------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -19,10 +19,44 @@
 #define LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H
 
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/IR/Function.h"
+#include "llvm/ADT/DenseMapInfo.h"
+#include <cstdint>
 
 namespace llvm {
 
+class BasicBlock;
+class Value;
+
+struct DivRemMapKey {
+  bool SignedOp;
+  Value *Dividend;
+  Value *Divisor;
+
+  DivRemMapKey(bool InSignedOp, Value *InDividend, Value *InDivisor)
+      : SignedOp(InSignedOp), Dividend(InDividend), Divisor(InDivisor) {}
+};
+
+template <> struct DenseMapInfo<DivRemMapKey> {
+  static bool isEqual(const DivRemMapKey &Val1, const DivRemMapKey &Val2) {
+    return Val1.SignedOp == Val2.SignedOp && Val1.Dividend == Val2.Dividend &&
+           Val1.Divisor == Val2.Divisor;
+  }
+
+  static DivRemMapKey getEmptyKey() {
+    return DivRemMapKey(false, nullptr, nullptr);
+  }
+
+  static DivRemMapKey getTombstoneKey() {
+    return DivRemMapKey(true, nullptr, nullptr);
+  }
+
+  static unsigned getHashValue(const DivRemMapKey &Val) {
+    return (unsigned)(reinterpret_cast<uintptr_t>(Val.Dividend) ^
+                      reinterpret_cast<uintptr_t>(Val.Divisor)) ^
+           (unsigned)Val.SignedOp;
+  }
+};
+
 /// This optimization identifies DIV instructions in a BB that can be
 /// profitably bypassed and carried out with a shorter, faster divide.
 ///
@@ -31,6 +65,6 @@ namespace llvm {
 bool bypassSlowDivision(
     BasicBlock *BB, const DenseMap<unsigned int, unsigned int> &BypassWidth);
 
-} // End llvm namespace
+} // end namespace llvm
 
-#endif
+#endif // LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H
diff --git a/include/llvm/Transforms/Utils/CallPromotionUtils.h b/include/llvm/Transforms/Utils/CallPromotionUtils.h
new file mode 100644
index 0000000000000..e0bf85781d811
--- /dev/null
+++ b/include/llvm/Transforms/Utils/CallPromotionUtils.h
@@ -0,0 +1,44 @@
+//===- CallPromotionUtils.h - Utilities for call promotion ------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file declares utilities useful for promoting indirect call sites to
+// direct call sites.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_CALLPROMOTIONUTILS_H
+#define LLVM_TRANSFORMS_UTILS_CALLPROMOTIONUTILS_H
+
+#include "llvm/IR/CallSite.h"
+
+namespace llvm {
+
+/// Return true if the given indirect call site can be made to call \p Callee.
+///
+/// This function ensures that the number and type of the call site's arguments
+/// and return value match those of the given function. If the types do not
+/// match exactly, they must at least be bitcast compatible. If \p FailureReason
+/// is non-null and the indirect call cannot be promoted, the failure reason
+/// will be stored in it.
+bool isLegalToPromote(CallSite CS, Function *Callee,
+                      const char **FailureReason = nullptr);
+
+/// Promote the given indirect call site to conditionally call \p Callee.
+///
+/// This function creates an if-then-else structure at the location of the call
+/// site. The original call site is promoted and moved into the "then" block. A
+/// clone of the indirect call site is placed in the "else" block and returned.
+/// If \p BranchWeights is non-null, it will be used to set !prof metadata on
+/// the new conditional branch.
+Instruction *promoteCallWithIfThenElse(CallSite CS, Function *Callee,
+                                       MDNode *BranchWeights = nullptr);
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_CALLPROMOTIONUTILS_H
diff --git a/include/llvm/Transforms/Utils/Cloning.h b/include/llvm/Transforms/Utils/Cloning.h
index 2a8b89d862821..178bae76cef64 100644
--- a/include/llvm/Transforms/Utils/Cloning.h
+++ b/include/llvm/Transforms/Utils/Cloning.h
@@ -227,12 +227,18 @@ public:
 /// *inlined* code to minimize the actual inserted code, it must not delete
 /// code in the caller as users of this routine may have pointers to
 /// instructions in the caller that need to remain stable.
+///
+/// If ForwardVarArgsTo is passed, inlining a function with varargs is allowed
+/// and all varargs at the callsite will be passed to any calls to
+/// ForwardVarArgsTo. The caller of InlineFunction has to make sure any varargs
+/// are only used by ForwardVarArgsTo.
 bool InlineFunction(CallInst *C, InlineFunctionInfo &IFI,
                     AAResults *CalleeAAR = nullptr, bool InsertLifetime = true);
 bool InlineFunction(InvokeInst *II, InlineFunctionInfo &IFI,
                     AAResults *CalleeAAR = nullptr, bool InsertLifetime = true);
 bool InlineFunction(CallSite CS, InlineFunctionInfo &IFI,
-                    AAResults *CalleeAAR = nullptr, bool InsertLifetime = true);
+                    AAResults *CalleeAAR = nullptr, bool InsertLifetime = true,
+                    Function *ForwardVarArgsTo = nullptr);
 
 /// \brief Clones a loop \p OrigLoop.  Returns the loop and the blocks in \p
 /// Blocks.
diff --git a/include/llvm/Transforms/Utils/CmpInstAnalysis.h b/include/llvm/Transforms/Utils/CmpInstAnalysis.h
deleted file mode 100644
index 5ec3888d4538c..0000000000000
--- a/include/llvm/Transforms/Utils/CmpInstAnalysis.h
+++ /dev/null
@@ -1,70 +0,0 @@
-//===-- CmpInstAnalysis.h - Utils to help fold compare insts ----*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file holds routines to help analyse compare instructions
-// and fold them into constants or other compare instructions
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_TRANSFORMS_UTILS_CMPINSTANALYSIS_H
-#define LLVM_TRANSFORMS_UTILS_CMPINSTANALYSIS_H
-
-#include "llvm/IR/InstrTypes.h"
-
-namespace llvm {
-  class ICmpInst;
-  class Value;
-
-  /// Encode a icmp predicate into a three bit mask. These bits are carefully
-  /// arranged to allow folding of expressions such as:
-  ///
-  ///      (A < B) | (A > B) --> (A != B)
-  ///
-  /// Note that this is only valid if the first and second predicates have the
-  /// same sign. It is illegal to do: (A u< B) | (A s> B)
-  ///
-  /// Three bits are used to represent the condition, as follows:
-  ///   0  A > B
-  ///   1  A == B
-  ///   2  A < B
-  ///
-  /// <=>  Value  Definition
-  /// 000     0   Always false
-  /// 001     1   A >  B
-  /// 010     2   A == B
-  /// 011     3   A >= B
-  /// 100     4   A <  B
-  /// 101     5   A != B
-  /// 110     6   A <= B
-  /// 111     7   Always true
-  ///
-  unsigned getICmpCode(const ICmpInst *ICI, bool InvertPred = false);
-
-  /// This is the complement of getICmpCode, which turns an opcode and two
-  /// operands into either a constant true or false, or the predicate for a new
-  /// ICmp instruction. The sign is passed in to determine which kind of
-  /// predicate to use in the new icmp instruction.
-  /// Non-NULL return value will be a true or false constant.
-  /// NULL return means a new ICmp is needed. The predicate for which is output
-  /// in NewICmpPred.
-  Value *getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS,
-                      CmpInst::Predicate &NewICmpPred);
-
-  /// Return true if both predicates match sign or if at least one of them is an
-  /// equality comparison (which is signless).
-  bool PredicatesFoldable(CmpInst::Predicate p1, CmpInst::Predicate p2);
-
-  /// Decompose an icmp into the form ((X & Y) pred Z) if possible. The returned
-  /// predicate is either == or !=. Returns false if decomposition fails.
-  bool decomposeBitTestICmp(const ICmpInst *I, CmpInst::Predicate &Pred,
-                            Value *&X, Value *&Y, Value *&Z);
-
-} // end namespace llvm
-
-#endif
diff --git a/include/llvm/Transforms/Utils/CodeExtractor.h b/include/llvm/Transforms/Utils/CodeExtractor.h
index 682b353ab5ae8..63d34511102dc 100644
--- a/include/llvm/Transforms/Utils/CodeExtractor.h
+++ b/include/llvm/Transforms/Utils/CodeExtractor.h
@@ -1,4 +1,4 @@
-//===-- Transform/Utils/CodeExtractor.h - Code extraction util --*- C++ -*-===//
+//===- Transform/Utils/CodeExtractor.h - Code extraction util ---*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -15,22 +15,24 @@
 #ifndef LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
 #define LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
 
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SetVector.h"
+#include <limits>
 
 namespace llvm {
-template <typename T> class ArrayRef;
-  class BasicBlock;
-  class BlockFrequency;
-  class BlockFrequencyInfo;
-  class BranchProbabilityInfo;
-  class DominatorTree;
-  class Function;
-  class Instruction;
-  class Loop;
-  class Module;
-  class RegionNode;
-  class Type;
-  class Value;
+
+class BasicBlock;
+class BlockFrequency;
+class BlockFrequencyInfo;
+class BranchProbabilityInfo;
+class DominatorTree;
+class Function;
+class Instruction;
+class Loop;
+class Module;
+class Type;
+class Value;
 
   /// \brief Utility class for extracting code into a new function.
   ///
@@ -46,7 +48,7 @@ template <typename T> class ArrayRef;
   /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas
   ///    as arguments, and inserting stores to the arguments for any scalars.
   class CodeExtractor {
-    typedef SetVector<Value *> ValueSet;
+    using ValueSet = SetVector<Value *>;
 
     // Various bits of state computed on construction.
     DominatorTree *const DT;
@@ -54,27 +56,27 @@ template <typename T> class ArrayRef;
     BlockFrequencyInfo *BFI;
     BranchProbabilityInfo *BPI;
 
+    // If true, varargs functions can be extracted.
+    bool AllowVarArgs;
+
     // Bits of intermediate state computed at various phases of extraction.
     SetVector<BasicBlock *> Blocks;
-    unsigned NumExitBlocks;
+    unsigned NumExitBlocks = std::numeric_limits<unsigned>::max();
     Type *RetTy;
 
   public:
-
-    /// \brief Check to see if a block is valid for extraction.
-    ///
-    /// Blocks containing EHPads, allocas, invokes, or vastarts are not valid.
-    static bool isBlockValidForExtraction(const BasicBlock &BB);
-
     /// \brief Create a code extractor for a sequence of blocks.
     ///
     /// Given a sequence of basic blocks where the first block in the sequence
     /// dominates the rest, prepare a code extractor object for pulling this
     /// sequence out into its new function. When a DominatorTree is also given,
-    /// extra checking and transformations are enabled.
+    /// extra checking and transformations are enabled. If AllowVarArgs is true,
+    /// vararg functions can be extracted. This is safe, if all vararg handling
+    /// code is extracted, including vastart.
     CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr,
                   bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr,
-                  BranchProbabilityInfo *BPI = nullptr);
+                  BranchProbabilityInfo *BPI = nullptr,
+                  bool AllowVarArgs = false);
 
     /// \brief Create a code extractor for a loop body.
     ///
@@ -84,6 +86,14 @@ template <typename T> class ArrayRef;
                   BlockFrequencyInfo *BFI = nullptr,
                   BranchProbabilityInfo *BPI = nullptr);
 
+    /// \brief Check to see if a block is valid for extraction.
+    ///
+    /// Blocks containing EHPads, allocas and invokes are not valid. If
+    /// AllowVarArgs is true, blocks with vastart can be extracted. This is
+    /// safe, if all vararg handling code is extracted, including vastart.
+    static bool isBlockValidForExtraction(const BasicBlock &BB,
+                                          bool AllowVarArgs);
+
     /// \brief Perform the extraction, returning the new function.
     ///
     /// Returns zero when called on a CodeExtractor instance where isEligible
@@ -112,6 +122,7 @@ template <typename T> class ArrayRef;
     ///
     /// Returns true if it is safe to do the code motion.
     bool isLegalToShrinkwrapLifetimeMarkers(Instruction *AllocaAddr) const;
+
     /// Find the set of allocas whose life ranges are contained within the
     /// outlined region.
     ///
@@ -155,6 +166,7 @@ template <typename T> class ArrayRef;
                                     ValueSet &inputs,
                                     ValueSet &outputs);
   };
-}
 
-#endif
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
diff --git a/include/llvm/Transforms/Utils/EntryExitInstrumenter.h b/include/llvm/Transforms/Utils/EntryExitInstrumenter.h
new file mode 100644
index 0000000000000..f50c5c9220816
--- /dev/null
+++ b/include/llvm/Transforms/Utils/EntryExitInstrumenter.h
@@ -0,0 +1,36 @@
+//===- EntryExitInstrumenter.h - Function Entry/Exit Instrumentation ------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// EntryExitInstrumenter pass - Instrument function entry/exit with calls to
+// mcount(), @__cyg_profile_func_{enter,exit} and the like. There are two
+// variants, intended to run pre- and post-inlining, respectively.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_ENTRYEXITINSTRUMENTER_H
+#define LLVM_TRANSFORMS_UTILS_ENTRYEXITINSTRUMENTER_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+class Function;
+
+struct EntryExitInstrumenterPass
+    : public PassInfoMixin<EntryExitInstrumenterPass> {
+  EntryExitInstrumenterPass(bool PostInlining) : PostInlining(PostInlining) {}
+
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+
+  bool PostInlining;
+};
+
+} // namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_ENTRYEXITINSTRUMENTER_H
diff --git a/include/llvm/Transforms/Utils/Evaluator.h b/include/llvm/Transforms/Utils/Evaluator.h
index 07f12f41b3bcd..0e987b93177aa 100644
--- a/include/llvm/Transforms/Utils/Evaluator.h
+++ b/include/llvm/Transforms/Utils/Evaluator.h
@@ -1,4 +1,4 @@
-//===-- Evaluator.h - LLVM IR evaluator -------------------------*- C++ -*-===//
+//===- Evaluator.h - LLVM IR evaluator --------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -18,9 +18,10 @@
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/Constant.h"
 #include "llvm/IR/GlobalVariable.h"
-
+#include "llvm/IR/Value.h"
+#include "llvm/Support/Casting.h"
+#include <cassert>
 #include <deque>
 #include <memory>
 
@@ -114,6 +115,6 @@ private:
   const TargetLibraryInfo *TLI;
 };
 
-}
+} // end namespace llvm
 
-#endif
+#endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H
diff --git a/include/llvm/Transforms/Utils/FunctionComparator.h b/include/llvm/Transforms/Utils/FunctionComparator.h
index b0f10eafaa95f..7698a068717a9 100644
--- a/include/llvm/Transforms/Utils/FunctionComparator.h
+++ b/include/llvm/Transforms/Utils/FunctionComparator.h
@@ -15,10 +15,10 @@
 #ifndef LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H
 #define LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H
 
-#include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringRef.h"
-#include "llvm/IR/Function.h"
+#include "llvm/IR/Attributes.h"
+#include "llvm/IR/Instructions.h" 
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/ValueMap.h"
 #include "llvm/Support/AtomicOrdering.h"
@@ -28,7 +28,17 @@
 
 namespace llvm {
 
-class GetElementPtrInst;
+class APFloat;
+class APInt;
+class BasicBlock;
+class Constant;
+class Function;
+class GlobalValue;
+class InlineAsm;
+class Instruction;
+class MDNode;
+class Type;
+class Value;
 
 /// GlobalNumberState assigns an integer to each global value in the program,
 /// which is used by the comparison routine to order references to globals. This
@@ -43,14 +53,16 @@ class GetElementPtrInst;
 /// compare those, but this would not work for stripped bitcodes or for those
 /// few symbols without a name.
 class GlobalNumberState {
-  struct Config : ValueMapConfig<GlobalValue*> {
+  struct Config : ValueMapConfig<GlobalValue *> {
     enum { FollowRAUW = false };
   };
+
   // Each GlobalValue is mapped to an identifier. The Config ensures when RAUW
   // occurs, the mapping does not change. Tracking changes is unnecessary, and
   // also problematic for weak symbols (which may be overwritten).
-  typedef ValueMap<GlobalValue *, uint64_t, Config> ValueNumberMap;
+  using ValueNumberMap = ValueMap<GlobalValue *, uint64_t, Config>;
   ValueNumberMap GlobalNumbers;
+
   // The next unused serial number to assign to a global.
   uint64_t NextNumber = 0;
 
@@ -66,6 +78,10 @@ public:
     return MapIter->second;
   }
 
+  void erase(GlobalValue *Global) {
+    GlobalNumbers.erase(Global);
+  }
+
   void clear() {
     GlobalNumbers.clear();
   }
@@ -83,9 +99,10 @@ public:
 
   /// Test whether the two functions have equivalent behaviour.
   int compare();
+
   /// Hash a function. Equivalent functions will have the same hash, and unequal
   /// functions will have different hashes with high probability.
-  typedef uint64_t FunctionHash;
+  using FunctionHash = uint64_t;
   static FunctionHash functionHash(Function &);
 
 protected:
diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h
index 30b27616cd982..01db88bc15c2f 100644
--- a/include/llvm/Transforms/Utils/Local.h
+++ b/include/llvm/Transforms/Utils/Local.h
@@ -1,4 +1,4 @@
-//===-- Local.h - Functions to perform local transformations ----*- C++ -*-===//
+//===- Local.h - Functions to perform local transformations -----*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -15,39 +15,95 @@
 #ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H
 #define LLVM_TRANSFORMS_UTILS_LOCAL_H
 
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/Constant.h"
+#include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
-#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Operator.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/User.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Support/Casting.h"
+#include <cstdint>
+#include <limits>
 
 namespace llvm {
 
-class User;
+class AllocaInst;
+class AssumptionCache;
 class BasicBlock;
-class Function;
 class BranchInst;
-class Instruction;
 class CallInst;
-class DbgDeclareInst;
+class DbgInfoIntrinsic;
 class DbgValueInst;
-class StoreInst;
+class DIBuilder;
+class Function;
+class Instruction;
+class LazyValueInfo;
 class LoadInst;
-class Value;
+class MDNode;
 class PHINode;
-class AllocaInst;
-class AssumptionCache;
-class ConstantExpr;
-class DataLayout;
+class StoreInst;
 class TargetLibraryInfo;
 class TargetTransformInfo;
-class DIBuilder;
-class DominatorTree;
-class LazyValueInfo;
 
-template<typename T> class SmallVectorImpl;
+/// A set of parameters used to control the transforms in the SimplifyCFG pass.
+/// Options may change depending on the position in the optimization pipeline.
+/// For example, canonical form that includes switches and branches may later be
+/// replaced by lookup tables and selects.
+struct SimplifyCFGOptions {
+  int BonusInstThreshold;
+  bool ForwardSwitchCondToPhi;
+  bool ConvertSwitchToLookupTable;
+  bool NeedCanonicalLoop;
+  bool SinkCommonInsts;
+  AssumptionCache *AC;
+
+  SimplifyCFGOptions(unsigned BonusThreshold = 1,
+                     bool ForwardSwitchCond = false,
+                     bool SwitchToLookup = false, bool CanonicalLoops = true,
+                     bool SinkCommon = false,
+                     AssumptionCache *AssumpCache = nullptr)
+      : BonusInstThreshold(BonusThreshold),
+        ForwardSwitchCondToPhi(ForwardSwitchCond),
+        ConvertSwitchToLookupTable(SwitchToLookup),
+        NeedCanonicalLoop(CanonicalLoops),
+        SinkCommonInsts(SinkCommon),
+        AC(AssumpCache) {}
+
+  // Support 'builder' pattern to set members by name at construction time.
+  SimplifyCFGOptions &bonusInstThreshold(int I) {
+    BonusInstThreshold = I;
+    return *this;
+  }
+  SimplifyCFGOptions &forwardSwitchCondToPhi(bool B) {
+    ForwardSwitchCondToPhi = B;
+    return *this;
+  }
+  SimplifyCFGOptions &convertSwitchToLookupTable(bool B) {
+    ConvertSwitchToLookupTable = B;
+    return *this;
+  }
+  SimplifyCFGOptions &needCanonicalLoops(bool B) {
+    NeedCanonicalLoop = B;
+    return *this;
+  }
+  SimplifyCFGOptions &sinkCommonInsts(bool B) {
+    SinkCommonInsts = B;
+    return *this;
+  }
+  SimplifyCFGOptions &setAssumptionCache(AssumptionCache *Cache) {
+    AC = Cache;
+    return *this;
+  }
+};
 
 //===----------------------------------------------------------------------===//
 //  Local constant propagation.
@@ -133,17 +189,15 @@ bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB);
 /// values, but instcombine orders them so it usually won't matter.
 bool EliminateDuplicatePHINodes(BasicBlock *BB);
 
-/// This function is used to do simplification of a CFG.  For
-/// example, it adjusts branches to branches to eliminate the extra hop, it
-/// eliminates unreachable basic blocks, and does other "peephole" optimization
-/// of the CFG.  It returns true if a modification was made, possibly deleting
-/// the basic block that was pointed to. LoopHeaders is an optional input
-/// parameter, providing the set of loop header that SimplifyCFG should not
-/// eliminate.
-bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
-                 unsigned BonusInstThreshold, AssumptionCache *AC = nullptr,
-                 SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr,
-                 bool LateSimplifyCFG = false);
+/// This function is used to do simplification of a CFG.  For example, it
+/// adjusts branches to branches to eliminate the extra hop, it eliminates
+/// unreachable basic blocks, and does other peephole optimization of the CFG.
+/// It returns true if a modification was made, possibly deleting the basic
+/// block that was pointed to. LoopHeaders is an optional input parameter
+/// providing the set of loop headers that SimplifyCFG should not eliminate.
+bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
+                 const SimplifyCFGOptions &Options = {},
+                 SmallPtrSetImpl<BasicBlock *> *LoopHeaders = nullptr);
 
 /// This function is used to flatten a CFG. For example, it uses parallel-and
 /// and parallel-or mode to collapse if-conditions and merge if-regions with
@@ -185,10 +239,10 @@ unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign,
                                     const DominatorTree *DT = nullptr);
 
 /// Try to infer an alignment for the specified pointer.
-static inline unsigned getKnownAlignment(Value *V, const DataLayout &DL,
-                                         const Instruction *CxtI = nullptr,
-                                         AssumptionCache *AC = nullptr,
-                                         const DominatorTree *DT = nullptr) {
+inline unsigned getKnownAlignment(Value *V, const DataLayout &DL,
+                                  const Instruction *CxtI = nullptr,
+                                  AssumptionCache *AC = nullptr,
+                                  const DominatorTree *DT = nullptr) {
   return getOrEnforceKnownAlignment(V, 0, DL, CxtI, AC, DT);
 }
 
@@ -210,7 +264,8 @@ Value *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP,
 
   // Build a mask for high order bits.
   unsigned IntPtrWidth = IntPtrTy->getScalarType()->getIntegerBitWidth();
-  uint64_t PtrSizeMask = ~0ULL >> (64 - IntPtrWidth);
+  uint64_t PtrSizeMask =
+      std::numeric_limits<uint64_t>::max() >> (64 - IntPtrWidth);
 
   gep_type_iterator GTI = gep_type_begin(GEP);
   for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e;
@@ -262,46 +317,50 @@ Value *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP,
 ///
 
 /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
-/// that has an associated llvm.dbg.decl intrinsic.
-void ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
+/// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
+void ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII,
                                      StoreInst *SI, DIBuilder &Builder);
 
 /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
-/// that has an associated llvm.dbg.decl intrinsic.
-void ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
+/// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
+void ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII,
                                      LoadInst *LI, DIBuilder &Builder);
 
-/// Inserts a llvm.dbg.value intrinsic after a phi of an alloca'd value
-/// that has an associated llvm.dbg.decl intrinsic.
-void ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
+/// Inserts a llvm.dbg.value intrinsic after a phi that has an associated
+/// llvm.dbg.declare or llvm.dbg.addr intrinsic.
+void ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII,
                                      PHINode *LI, DIBuilder &Builder);
 
 /// Lowers llvm.dbg.declare intrinsics into appropriate set of
 /// llvm.dbg.value intrinsics.
 bool LowerDbgDeclare(Function &F);
 
-/// Finds the llvm.dbg.declare intrinsic corresponding to an alloca, if any.
-DbgDeclareInst *FindAllocaDbgDeclare(Value *V);
+/// Finds all intrinsics declaring local variables as living in the memory that
+/// 'V' points to. This may include a mix of dbg.declare and
+/// dbg.addr intrinsics.
+TinyPtrVector<DbgInfoIntrinsic *> FindDbgAddrUses(Value *V);
 
 /// Finds the llvm.dbg.value intrinsics describing a value.
 void findDbgValues(SmallVectorImpl<DbgValueInst *> &DbgValues, Value *V);
 
-/// Replaces llvm.dbg.declare instruction when the address it describes
-/// is replaced with a new value. If Deref is true, an additional DW_OP_deref is
-/// prepended to the expression. If Offset is non-zero, a constant displacement
-/// is added to the expression (after the optional Deref). Offset can be
-/// negative.
+/// Replaces llvm.dbg.declare instruction when the address it
+/// describes is replaced with a new value. If Deref is true, an
+/// additional DW_OP_deref is prepended to the expression. If Offset
+/// is non-zero, a constant displacement is added to the expression
+/// (between the optional Deref operations). Offset can be negative.
 bool replaceDbgDeclare(Value *Address, Value *NewAddress,
                        Instruction *InsertBefore, DIBuilder &Builder,
-                       bool Deref, int Offset);
+                       bool DerefBefore, int Offset, bool DerefAfter);
 
 /// Replaces llvm.dbg.declare instruction when the alloca it describes
-/// is replaced with a new value. If Deref is true, an additional DW_OP_deref is
-/// prepended to the expression. If Offset is non-zero, a constant displacement
-/// is added to the expression (after the optional Deref). Offset can be
-/// negative. New llvm.dbg.declare is inserted immediately before AI.
+/// is replaced with a new value. If Deref is true, an additional
+/// DW_OP_deref is prepended to the expression. If Offset is non-zero,
+/// a constant displacement is added to the expression (between the
+/// optional Deref operations). Offset can be negative. The new
+/// llvm.dbg.declare is inserted immediately before AI.
 bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
-                                DIBuilder &Builder, bool Deref, int Offset = 0);
+                                DIBuilder &Builder, bool DerefBefore,
+                                int Offset, bool DerefAfter);
 
 /// Replaces multiple llvm.dbg.value instructions when the alloca it describes
 /// is replaced with a new value. If Offset is non-zero, a constant displacement
@@ -369,7 +428,6 @@ unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT,
 unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT,
                                   const BasicBlock *BB);
 
-
 /// Return true if the CallSite CS calls a gc leaf function.
 ///
 /// A leaf function is a function that does not safepoint the thread during its
@@ -378,7 +436,7 @@ unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT,
 ///
 /// Most passes can and should ignore this information, and it is only used
 /// during lowering by the GC infrastructure.
-bool callsGCLeafFunction(ImmutableCallSite CS);
+bool callsGCLeafFunction(ImmutableCallSite CS, const TargetLibraryInfo &TLI);
 
 /// Copy a nonnull metadata node to a new load instruction.
 ///
@@ -397,7 +455,7 @@ void copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, MDNode *N,
 //  Intrinsic pattern matching
 //
 
-/// Try and match a bswap or bitreverse idiom.
+/// Try to match a bswap or bitreverse idiom.
 ///
 /// If an idiom is matched, an intrinsic call is inserted before \c I. Any added
 /// instructions are returned in \c InsertedInsts. They will all have been added
@@ -431,6 +489,6 @@ void maybeMarkSanitizerLibraryCallNoBuiltin(CallInst *CI,
 /// value?
 bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx);
 
-} // End llvm namespace
+} // end namespace llvm
 
-#endif
+#endif // LLVM_TRANSFORMS_UTILS_LOCAL_H
diff --git a/include/llvm/Transforms/Utils/LoopUtils.h b/include/llvm/Transforms/Utils/LoopUtils.h
index 94e20b83754e7..7506661365070 100644
--- a/include/llvm/Transforms/Utils/LoopUtils.h
+++ b/include/llvm/Transforms/Utils/LoopUtils.h
@@ -16,6 +16,7 @@
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
@@ -305,10 +306,13 @@ public:
   /// induction, the induction descriptor \p D will contain the data describing
   /// this induction. If by some other means the caller has a better SCEV
   /// expression for \p Phi than the one returned by the ScalarEvolution
-  /// analysis, it can be passed through \p Expr.
-  static bool isInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE,
-                             InductionDescriptor &D,
-                             const SCEV *Expr = nullptr);
+  /// analysis, it can be passed through \p Expr. If the def-use chain 
+  /// associated with the phi includes casts (that we know we can ignore
+  /// under proper runtime checks), they are passed through \p CastsToIgnore.
+  static bool 
+  isInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE,
+                 InductionDescriptor &D, const SCEV *Expr = nullptr,
+                 SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr);
 
   /// Returns true if \p Phi is a floating point induction in the loop \p L.
   /// If \p Phi is an induction, the induction descriptor \p D will contain 
@@ -330,15 +334,13 @@ public:
   /// not have the "fast-math" property. Such operation requires a relaxed FP
   /// mode.
   bool hasUnsafeAlgebra() {
-    return InductionBinOp &&
-      !cast<FPMathOperator>(InductionBinOp)->hasUnsafeAlgebra();
+    return InductionBinOp && !cast<FPMathOperator>(InductionBinOp)->isFast();
   }
 
   /// Returns induction operator that does not have "fast-math" property
   /// and requires FP unsafe mode.
   Instruction *getUnsafeAlgebraInst() {
-    if (!InductionBinOp ||
-        cast<FPMathOperator>(InductionBinOp)->hasUnsafeAlgebra())
+    if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast())
       return nullptr;
     return InductionBinOp;
   }
@@ -349,10 +351,18 @@ public:
       Instruction::BinaryOpsEnd;
   }
 
+  /// Returns a reference to the type cast instructions in the induction 
+  /// update chain, that are redundant when guarded with a runtime
+  /// SCEV overflow check.
+  const SmallVectorImpl<Instruction *> &getCastInsts() const { 
+    return RedundantCasts; 
+  }
+
 private:
   /// Private constructor - used by \c isInductionPHI.
   InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
-                      BinaryOperator *InductionBinOp = nullptr);
+                      BinaryOperator *InductionBinOp = nullptr,
+                      SmallVectorImpl<Instruction *> *Casts = nullptr);
 
   /// Start value.
   TrackingVH<Value> StartValue;
@@ -362,6 +372,9 @@ private:
   const SCEV *Step = nullptr;
   // Instruction that advances induction variable.
   BinaryOperator *InductionBinOp = nullptr;
+  // Instructions used for type-casts of the induction variable,
+  // that are redundant when guarded with a runtime SCEV overflow check.
+  SmallVector<Instruction *, 2> RedundantCasts;
 };
 
 BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
@@ -423,8 +436,9 @@ bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
 /// instructions of the loop and loop safety information as
 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
-                TargetLibraryInfo *, Loop *, AliasSetTracker *,
-                LoopSafetyInfo *, OptimizationRemarkEmitter *ORE);
+                TargetLibraryInfo *, TargetTransformInfo *, Loop *,
+                AliasSetTracker *, LoopSafetyInfo *,
+                OptimizationRemarkEmitter *ORE);
 
 /// \brief Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in depth
@@ -438,21 +452,41 @@ bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
                  LoopSafetyInfo *, OptimizationRemarkEmitter *ORE);
 
+/// This function deletes dead loops. The caller of this function needs to
+/// guarantee that the loop is infact dead.
+/// The function requires a bunch or prerequisites to be present:
+///   - The loop needs to be in LCSSA form
+///   - The loop needs to have a Preheader
+///   - A unique dedicated exit block must exist
+///
+/// This also updates the relevant analysis information in \p DT, \p SE, and \p
+/// LI if pointers to those are provided.
+/// It also updates the loop PM if an updater struct is provided.
+
+void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE,
+                    LoopInfo *LI);
+
 /// \brief Try to promote memory values to scalars by sinking stores out of
 /// the loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
-/// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
-/// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop,
-/// AliasSet information for all instructions of the loop and loop safety
-/// information as arguments. Diagnostics is emitted via \p ORE. It returns
-/// changed status.
-bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock *> &,
+/// loop invariant. It takes a set of must-alias values, Loop exit blocks
+/// vector, loop exit blocks insertion point vector, PredIteratorCache,
+/// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions
+/// of the loop and loop safety information as arguments.
+/// Diagnostics is emitted via \p ORE. It returns changed status.
+bool promoteLoopAccessesToScalars(const SmallSetVector<Value *, 8> &,
+                                  SmallVectorImpl<BasicBlock *> &,
                                   SmallVectorImpl<Instruction *> &,
                                   PredIteratorCache &, LoopInfo *,
                                   DominatorTree *, const TargetLibraryInfo *,
                                   Loop *, AliasSetTracker *, LoopSafetyInfo *,
                                   OptimizationRemarkEmitter *);
 
+/// Does a BFS from a given node to all of its children inside a given loop.
+/// The returned vector of nodes includes the starting point.
+SmallVector<DomTreeNode *, 16> collectChildrenInLoop(DomTreeNode *N,
+                                                     const Loop *CurLoop);
+
 /// \brief Computes safety information for a loop
 /// checks loop body & header for the possibility of may throw
 /// exception, it takes LoopSafetyInfo and loop as argument.
diff --git a/include/llvm/Transforms/Utils/LowerMemIntrinsics.h b/include/llvm/Transforms/Utils/LowerMemIntrinsics.h
index 4554b5cbc6440..2b7d0f67a3245 100644
--- a/include/llvm/Transforms/Utils/LowerMemIntrinsics.h
+++ b/include/llvm/Transforms/Utils/LowerMemIntrinsics.h
@@ -25,12 +25,6 @@ class MemSetInst;
 class TargetTransformInfo;
 class Value;
 
-/// Emit a loop implementing the semantics of llvm.memcpy with the equivalent
-/// arguments at \p InsertBefore.
-void createMemCpyLoop(Instruction *InsertBefore, Value *SrcAddr, Value *DstAddr,
-                      Value *CopyLen, unsigned SrcAlign, unsigned DestAlign,
-                      bool SrcIsVolatile, bool DstIsVolatile);
-
 /// Emit a loop implementing the semantics of llvm.memcpy where the size is not
 /// a compile-time constant. Loop will be insterted at \p InsertBefore.
 void createMemCpyLoopUnknownSize(Instruction *InsertBefore, Value *SrcAddr,
diff --git a/include/llvm/Transforms/Utils/Mem2Reg.h b/include/llvm/Transforms/Utils/Mem2Reg.h
index 1fe186d6c3ad9..407684338a3b7 100644
--- a/include/llvm/Transforms/Utils/Mem2Reg.h
+++ b/include/llvm/Transforms/Utils/Mem2Reg.h
@@ -15,14 +15,17 @@
 #ifndef LLVM_TRANSFORMS_UTILS_MEM2REG_H
 #define LLVM_TRANSFORMS_UTILS_MEM2REG_H
 
-#include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
+
+class Function;
+
 class PromotePass : public PassInfoMixin<PromotePass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
-}
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_MEM2REG_H
diff --git a/include/llvm/Transforms/Utils/ModuleUtils.h b/include/llvm/Transforms/Utils/ModuleUtils.h
index e9793fe4b6666..4b9bc82938106 100644
--- a/include/llvm/Transforms/Utils/ModuleUtils.h
+++ b/include/llvm/Transforms/Utils/ModuleUtils.h
@@ -85,7 +85,8 @@ void filterDeadComdatFunctions(
     Module &M, SmallVectorImpl<Function *> &DeadComdatFunctions);
 
 /// \brief Produce a unique identifier for this module by taking the MD5 sum of
-/// the names of the module's strong external symbols.
+/// the names of the module's strong external symbols that are not comdat
+/// members.
 ///
 /// This identifier is normally guaranteed to be unique, or the program would
 /// fail to link due to multiply defined symbols.
diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h
index 8cbcdf47156ea..6cd9f1539b0b3 100644
--- a/include/llvm/Transforms/Utils/SSAUpdater.h
+++ b/include/llvm/Transforms/Utils/SSAUpdater.h
@@ -1,4 +1,4 @@
-//===-- SSAUpdater.h - Unstructured SSA Update Tool -------------*- C++ -*-===//
+//===- SSAUpdater.h - Unstructured SSA Update Tool --------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -14,6 +14,7 @@
 #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H
 #define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H
 
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/StringRef.h"
 #include <string>
 
@@ -22,10 +23,9 @@ namespace llvm {
 class BasicBlock;
 class Instruction;
 class LoadInst;
-template <typename T> class ArrayRef;
+class PHINode;
 template <typename T> class SmallVectorImpl;
 template <typename T> class SSAUpdaterTraits;
-class PHINode;
 class Type;
 class Use;
 class Value;
@@ -42,7 +42,6 @@ class SSAUpdater {
 private:
   /// This keeps track of which value to use on a per-block basis. When we
   /// insert PHI nodes, we keep track of them here.
-  //typedef DenseMap<BasicBlock*, Value*> AvailableValsTy;
   void *AV = nullptr;
 
   /// ProtoType holds the type of the values being rewritten.
@@ -53,12 +52,12 @@ private:
 
   /// If this is non-null, the SSAUpdater adds all PHI nodes that it creates to
   /// the vector.
-  SmallVectorImpl<PHINode*> *InsertedPHIs;
+  SmallVectorImpl<PHINode *> *InsertedPHIs;
 
 public:
   /// If InsertedPHIs is specified, it will be filled
   /// in with all PHI Nodes created by rewriting.
-  explicit SSAUpdater(SmallVectorImpl<PHINode*> *InsertedPHIs = nullptr);
+  explicit SSAUpdater(SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr);
   SSAUpdater(const SSAUpdater &) = delete;
   SSAUpdater &operator=(const SSAUpdater &) = delete;
   ~SSAUpdater();
@@ -136,7 +135,7 @@ protected:
   SSAUpdater &SSA;
 
 public:
-  LoadAndStorePromoter(ArrayRef<const Instruction*> Insts,
+  LoadAndStorePromoter(ArrayRef<const Instruction *> Insts,
                        SSAUpdater &S, StringRef Name = StringRef());
   virtual ~LoadAndStorePromoter() = default;
 
@@ -145,32 +144,28 @@ public:
   /// Insts is a list of loads and stores to promote, and Name is the basename
   /// for the PHIs to insert. After this is complete, the loads and stores are
   /// removed from the code.
-  void run(const SmallVectorImpl<Instruction*> &Insts) const;
+  void run(const SmallVectorImpl<Instruction *> &Insts) const;
 
   /// \brief Return true if the specified instruction is in the Inst list.
   ///
   /// The Insts list is the one passed into the constructor. Clients should
   /// implement this with a more efficient version if possible.
   virtual bool isInstInList(Instruction *I,
-                            const SmallVectorImpl<Instruction*> &Insts) const;
+                            const SmallVectorImpl<Instruction *> &Insts) const;
 
   /// \brief This hook is invoked after all the stores are found and inserted as
   /// available values.
-  virtual void doExtraRewritesBeforeFinalDeletion() const {
-  }
+  virtual void doExtraRewritesBeforeFinalDeletion() const {}
 
   /// \brief Clients can choose to implement this to get notified right before
   /// a load is RAUW'd another value.
-  virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const {
-  }
+  virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const {}
 
   /// \brief Called before each instruction is deleted.
-  virtual void instructionDeleted(Instruction *I) const {
-  }
+  virtual void instructionDeleted(Instruction *I) const {}
 
   /// \brief Called to update debug info associated with the instruction.
-  virtual void updateDebugInfo(Instruction *I) const {
-  }
+  virtual void updateDebugInfo(Instruction *I) const {}
 };
 
 } // end namespace llvm
diff --git a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h
index 2dd205d8b2af2..b1611d49a456e 100644
--- a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h
+++ b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h
@@ -1,4 +1,4 @@
-//===-- SSAUpdaterImpl.h - SSA Updater Implementation -----------*- C++ -*-===//
+//===- SSAUpdaterImpl.h - SSA Updater Implementation ------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -17,17 +17,14 @@
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
-#include "llvm/IR/Instructions.h"
-#include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
 
 #define DEBUG_TYPE "ssaupdater"
 
 namespace llvm {
 
-class CastInst;
-class PHINode;
 template<typename T> class SSAUpdaterTraits;
 
 template<typename UpdaterT>
@@ -35,51 +32,67 @@ class SSAUpdaterImpl {
 private:
   UpdaterT *Updater;
 
-  typedef SSAUpdaterTraits<UpdaterT> Traits;
-  typedef typename Traits::BlkT BlkT;
-  typedef typename Traits::ValT ValT;
-  typedef typename Traits::PhiT PhiT;
+  using Traits = SSAUpdaterTraits<UpdaterT>;
+  using BlkT = typename Traits::BlkT;
+  using ValT = typename Traits::ValT;
+  using PhiT = typename Traits::PhiT;
 
   /// BBInfo - Per-basic block information used internally by SSAUpdaterImpl.
   /// The predecessors of each block are cached here since pred_iterator is
   /// slow and we need to iterate over the blocks at least a few times.
   class BBInfo {
   public:
-    BlkT *BB;          // Back-pointer to the corresponding block.
-    ValT AvailableVal; // Value to use in this block.
-    BBInfo *DefBB;     // Block that defines the available value.
-    int BlkNum;        // Postorder number.
-    BBInfo *IDom;      // Immediate dominator.
-    unsigned NumPreds; // Number of predecessor blocks.
-    BBInfo **Preds;    // Array[NumPreds] of predecessor blocks.
-    PhiT *PHITag;      // Marker for existing PHIs that match.
+    // Back-pointer to the corresponding block.
+    BlkT *BB;
+
+    // Value to use in this block.
+    ValT AvailableVal;
+
+    // Block that defines the available value.
+    BBInfo *DefBB;
+
+    // Postorder number.
+    int BlkNum = 0;
+
+    // Immediate dominator.
+    BBInfo *IDom = nullptr;
+
+    // Number of predecessor blocks.
+    unsigned NumPreds = 0;
+
+    // Array[NumPreds] of predecessor blocks.
+    BBInfo **Preds = nullptr;
+
+    // Marker for existing PHIs that match.
+    PhiT *PHITag = nullptr;
 
     BBInfo(BlkT *ThisBB, ValT V)
-      : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr), BlkNum(0),
-        IDom(nullptr), NumPreds(0), Preds(nullptr), PHITag(nullptr) {}
+      : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr) {}
   };
 
-  typedef DenseMap<BlkT*, ValT> AvailableValsTy;
+  using AvailableValsTy = DenseMap<BlkT *, ValT>;
+
   AvailableValsTy *AvailableVals;
 
-  SmallVectorImpl<PhiT*> *InsertedPHIs;
+  SmallVectorImpl<PhiT *> *InsertedPHIs;
+
+  using BlockListTy = SmallVectorImpl<BBInfo *>;
+  using BBMapTy = DenseMap<BlkT *, BBInfo *>;
 
-  typedef SmallVectorImpl<BBInfo*> BlockListTy;
-  typedef DenseMap<BlkT*, BBInfo*> BBMapTy;
   BBMapTy BBMap;
   BumpPtrAllocator Allocator;
 
 public:
   explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A,
-                          SmallVectorImpl<PhiT*> *Ins) :
-    Updater(U), AvailableVals(A), InsertedPHIs(Ins) { }
+                          SmallVectorImpl<PhiT *> *Ins) :
+    Updater(U), AvailableVals(A), InsertedPHIs(Ins) {}
 
   /// GetValue - Check to see if AvailableVals has an entry for the specified
   /// BB and if so, return it.  If not, construct SSA form by first
   /// calculating the required placement of PHIs and then inserting new PHIs
   /// where needed.
   ValT GetValue(BlkT *BB) {
-    SmallVector<BBInfo*, 100> BlockList;
+    SmallVector<BBInfo *, 100> BlockList;
     BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);
 
     // Special case: bail out if BB is unreachable.
@@ -101,8 +114,8 @@ public:
   /// Create BBInfo structures for the blocks and append them to the block
   /// list.
   BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
-    SmallVector<BBInfo*, 10> RootList;
-    SmallVector<BBInfo*, 64> WorkList;
+    SmallVector<BBInfo *, 10> RootList;
+    SmallVector<BBInfo *, 64> WorkList;
 
     BBInfo *Info = new (Allocator) BBInfo(BB, 0);
     BBMap[BB] = Info;
@@ -111,7 +124,7 @@ public:
     // Search backward from BB, creating BBInfos along the way and stopping
     // when reaching blocks that define the value.  Record those defining
     // blocks on the RootList.
-    SmallVector<BlkT*, 10> Preds;
+    SmallVector<BlkT *, 10> Preds;
     while (!WorkList.empty()) {
       Info = WorkList.pop_back_val();
       Preds.clear();
@@ -395,7 +408,7 @@ public:
   /// CheckIfPHIMatches - Check if a PHI node matches the placement and values
   /// in the BBMap.
   bool CheckIfPHIMatches(PhiT *PHI) {
-    SmallVector<PhiT*, 20> WorkList;
+    SmallVector<PhiT *, 20> WorkList;
     WorkList.push_back(PHI);
 
     // Mark that the block containing this PHI has been visited.
@@ -453,7 +466,7 @@ public:
   }
 };
 
-} // end llvm namespace
+} // end namespace llvm
 
 #undef DEBUG_TYPE // "ssaupdater"
 
diff --git a/include/llvm/Transforms/Utils/SimplifyIndVar.h b/include/llvm/Transforms/Utils/SimplifyIndVar.h
index 8d50aeb10d6eb..a1dfed29a22d3 100644
--- a/include/llvm/Transforms/Utils/SimplifyIndVar.h
+++ b/include/llvm/Transforms/Utils/SimplifyIndVar.h
@@ -26,6 +26,7 @@ class Loop;
 class LoopInfo;
 class PHINode;
 class ScalarEvolution;
+class SCEVExpander;
 
 /// Interface for visiting interesting IV users that are recognized but not
 /// simplified by this utility.
@@ -47,7 +48,7 @@ public:
 /// by using ScalarEvolution to analyze the IV's recurrence.
 bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT,
                        LoopInfo *LI, SmallVectorImpl<WeakTrackingVH> &Dead,
-                       IVVisitor *V = nullptr);
+                       SCEVExpander &Rewriter, IVVisitor *V = nullptr);
 
 /// SimplifyLoopIVs - Simplify users of induction variables within this
 /// loop. This does not actually change or add IVs.
diff --git a/include/llvm/Transforms/Utils/SimplifyLibCalls.h b/include/llvm/Transforms/Utils/SimplifyLibCalls.h
index 6aba9b2298b10..73a62f59203b4 100644
--- a/include/llvm/Transforms/Utils/SimplifyLibCalls.h
+++ b/include/llvm/Transforms/Utils/SimplifyLibCalls.h
@@ -28,6 +28,7 @@ class Instruction;
 class TargetLibraryInfo;
 class BasicBlock;
 class Function;
+class OptimizationRemarkEmitter;
 
 /// \brief This class implements simplifications for calls to fortified library
 /// functions (__st*cpy_chk, __memcpy_chk, __memmove_chk, __memset_chk), to,
@@ -73,6 +74,7 @@ private:
   FortifiedLibCallSimplifier FortifiedSimplifier;
   const DataLayout &DL;
   const TargetLibraryInfo *TLI;
+  OptimizationRemarkEmitter &ORE;
   bool UnsafeFPShrink;
   function_ref<void(Instruction *, Value *)> Replacer;
 
@@ -87,6 +89,7 @@ private:
 
 public:
   LibCallSimplifier(const DataLayout &DL, const TargetLibraryInfo *TLI,
+                    OptimizationRemarkEmitter &ORE,
                     function_ref<void(Instruction *, Value *)> Replacer =
                         &replaceAllUsesWithDefault);
 
@@ -126,14 +129,19 @@ private:
   Value *optimizeStringMemoryLibCall(CallInst *CI, IRBuilder<> &B);
 
   // Math Library Optimizations
+  Value *optimizeCAbs(CallInst *CI, IRBuilder<> &B);
   Value *optimizeCos(CallInst *CI, IRBuilder<> &B);
   Value *optimizePow(CallInst *CI, IRBuilder<> &B);
+  Value *replacePowWithSqrt(CallInst *Pow, IRBuilder<> &B);
   Value *optimizeExp2(CallInst *CI, IRBuilder<> &B);
   Value *optimizeFMinFMax(CallInst *CI, IRBuilder<> &B);
   Value *optimizeLog(CallInst *CI, IRBuilder<> &B);
   Value *optimizeSqrt(CallInst *CI, IRBuilder<> &B);
   Value *optimizeSinCosPi(CallInst *CI, IRBuilder<> &B);
   Value *optimizeTan(CallInst *CI, IRBuilder<> &B);
+  // Wrapper for all floating point library call optimizations
+  Value *optimizeFloatingPointLibCall(CallInst *CI, LibFunc Func,
+                                      IRBuilder<> &B);
 
   // Integer Library Call Optimizations
   Value *optimizeFFS(CallInst *CI, IRBuilder<> &B);
diff --git a/include/llvm/Transforms/Utils/SplitModule.h b/include/llvm/Transforms/Utils/SplitModule.h
index b7a3bcf4f86a5..d2c31f2701acc 100644
--- a/include/llvm/Transforms/Utils/SplitModule.h
+++ b/include/llvm/Transforms/Utils/SplitModule.h
@@ -22,7 +22,6 @@
 namespace llvm {
 
 class Module;
-class StringRef;
 
 /// Splits the module M into N linkable partitions. The function ModuleCallback
 /// is called N times passing each individual partition as the MPart argument.
@@ -39,6 +38,6 @@ void SplitModule(
     function_ref<void(std::unique_ptr<Module> MPart)> ModuleCallback,
     bool PreserveLocals = false);
 
-} // End llvm namespace
+} // end namespace llvm
 
-#endif
+#endif // LLVM_TRANSFORMS_UTILS_SPLITMODULE_H
diff --git a/include/llvm/Transforms/Utils/SymbolRewriter.h b/include/llvm/Transforms/Utils/SymbolRewriter.h
index 93658989fba57..e0caf7741ff39 100644
--- a/include/llvm/Transforms/Utils/SymbolRewriter.h
+++ b/include/llvm/Transforms/Utils/SymbolRewriter.h
@@ -1,4 +1,4 @@
-//===-- SymbolRewriter.h - Symbol Rewriting Pass ----------------*- C++ -*-===//
+//===- SymbolRewriter.h - Symbol Rewriting Pass -----------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -33,7 +33,6 @@
 #ifndef LLVM_TRANSFORMS_UTILS_SYMBOLREWRITER_H
 #define LLVM_TRANSFORMS_UTILS_SYMBOLREWRITER_H
 
-#include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 #include <list>
 #include <memory>
@@ -42,6 +41,8 @@
 namespace llvm {
 
 class MemoryBuffer;
+class Module;
+class ModulePass;
 
 namespace yaml {
 
@@ -89,7 +90,7 @@ private:
   const Type Kind;
 };
 
-typedef std::list<std::unique_ptr<RewriteDescriptor>> RewriteDescriptorList;
+using RewriteDescriptorList = std::list<std::unique_ptr<RewriteDescriptor>>;
 
 class RewriteMapParser {
 public:
@@ -120,6 +121,7 @@ ModulePass *createRewriteSymbolsPass(SymbolRewriter::RewriteDescriptorList &);
 class RewriteSymbolPass : public PassInfoMixin<RewriteSymbolPass> {
 public:
   RewriteSymbolPass() { loadAndParseMapFiles(); }
+
   RewriteSymbolPass(SymbolRewriter::RewriteDescriptorList &DL) {
     Descriptors.splice(Descriptors.begin(), DL);
   }
diff --git a/include/llvm/Transforms/Utils/UnrollLoop.h b/include/llvm/Transforms/Utils/UnrollLoop.h
index a3115ad16914d..12aa3bc6e7709 100644
--- a/include/llvm/Transforms/Utils/UnrollLoop.h
+++ b/include/llvm/Transforms/Utils/UnrollLoop.h
@@ -16,40 +16,57 @@
 #ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
 #define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
 
-// Needed because we can't forward-declare the nested struct
-// TargetTransformInfo::UnrollingPreferences
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 
 namespace llvm {
 
-class StringRef;
 class AssumptionCache;
+class BasicBlock;
 class DominatorTree;
 class Loop;
 class LoopInfo;
-class LPPassManager;
 class MDNode;
-class Pass;
 class OptimizationRemarkEmitter;
 class ScalarEvolution;
 
-typedef SmallDenseMap<const Loop *, Loop *, 4> NewLoopsMap;
+using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>;
 
 const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
                                      BasicBlock *ClonedBB, LoopInfo *LI,
                                      NewLoopsMap &NewLoops);
 
-bool UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool Force,
-                bool AllowRuntime, bool AllowExpensiveTripCount,
-                bool PreserveCondBr, bool PreserveOnlyFirst,
-                unsigned TripMultiple, unsigned PeelCount, LoopInfo *LI,
-                ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC,
-                OptimizationRemarkEmitter *ORE, bool PreserveLCSSA);
+/// Represents the result of a \c UnrollLoop invocation.
+enum class LoopUnrollResult {
+  /// The loop was not modified.
+  Unmodified,
+
+  /// The loop was partially unrolled -- we still have a loop, but with a
+  /// smaller trip count.  We may also have emitted epilogue loop if the loop
+  /// had a non-constant trip count.
+  PartiallyUnrolled,
+
+  /// The loop was fully unrolled into straight-line code.  We no longer have
+  /// any back-edges.
+  FullyUnrolled
+};
+
+LoopUnrollResult UnrollLoop(Loop *L, unsigned Count, unsigned TripCount,
+                            bool Force, bool AllowRuntime,
+                            bool AllowExpensiveTripCount, bool PreserveCondBr,
+                            bool PreserveOnlyFirst, unsigned TripMultiple,
+                            unsigned PeelCount, bool UnrollRemainder,
+                            LoopInfo *LI, ScalarEvolution *SE,
+                            DominatorTree *DT, AssumptionCache *AC,
+                            OptimizationRemarkEmitter *ORE, bool PreserveLCSSA);
 
 bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
                                 bool AllowExpensiveTripCount,
-                                bool UseEpilogRemainder, LoopInfo *LI,
+                                bool UseEpilogRemainder, bool UnrollRemainder,
+                                LoopInfo *LI,
                                 ScalarEvolution *SE, DominatorTree *DT,
+                                AssumptionCache *AC,
                                 bool PreserveLCSSA);
 
 void computePeelCount(Loop *L, unsigned LoopSize,
@@ -60,6 +77,7 @@ bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE,
               DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA);
 
 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name);
-}
 
-#endif
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
diff --git a/include/llvm/Transforms/Utils/ValueMapper.h b/include/llvm/Transforms/Utils/ValueMapper.h
index 45ef8246dcd16..4ecb23ea19518 100644
--- a/include/llvm/Transforms/Utils/ValueMapper.h
+++ b/include/llvm/Transforms/Utils/ValueMapper.h
@@ -21,9 +21,17 @@
 
 namespace llvm {
 
-class Value;
+class Constant;
+class Function;
+class GlobalAlias;
+class GlobalVariable;
 class Instruction;
-typedef ValueMap<const Value *, WeakTrackingVH> ValueToValueMapTy;
+class MDNode;
+class Metadata;
+class Type;
+class Value;
+
+using ValueToValueMapTy = ValueMap<const Value *, WeakTrackingVH>;
 
 /// This is a class that can be implemented by clients to remap types when
 /// cloning constants and instructions.
@@ -44,10 +52,10 @@ class ValueMaterializer {
   virtual void anchor(); // Out of line method.
 
 protected:
-  ~ValueMaterializer() = default;
   ValueMaterializer() = default;
   ValueMaterializer(const ValueMaterializer &) = default;
   ValueMaterializer &operator=(const ValueMaterializer &) = default;
+  ~ValueMaterializer() = default;
 
 public:
   /// This method can be implemented to generate a mapped Value on demand. For
@@ -91,7 +99,7 @@ enum RemapFlags {
   RF_NullMapMissingGlobalValues = 8,
 };
 
-static inline RemapFlags operator|(RemapFlags LHS, RemapFlags RHS) {
+inline RemapFlags operator|(RemapFlags LHS, RemapFlags RHS) {
   return RemapFlags(unsigned(LHS) | unsigned(RHS));
 }
 
diff --git a/include/llvm/Transforms/Vectorize/LoopVectorize.h b/include/llvm/Transforms/Vectorize/LoopVectorize.h
index 57d10c4c74734..32b56d372ea16 100644
--- a/include/llvm/Transforms/Vectorize/LoopVectorize.h
+++ b/include/llvm/Transforms/Vectorize/LoopVectorize.h
@@ -1,4 +1,4 @@
-//===---- LoopVectorize.h ---------------------------------------*- C++ -*-===//
+//===- LoopVectorize.h ------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -49,27 +49,29 @@
 #ifndef LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H
 #define LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H
 
-#include "llvm/ADT/MapVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
-#include "llvm/Analysis/AssumptionCache.h"
-#include "llvm/Analysis/BasicAliasAnalysis.h"
-#include "llvm/Analysis/BlockFrequencyInfo.h"
-#include "llvm/Analysis/DemandedBits.h"
-#include "llvm/Analysis/LoopAccessAnalysis.h"
-#include "llvm/Analysis/LoopInfo.h"
-#include "llvm/Analysis/OptimizationDiagnosticInfo.h"
-#include "llvm/Analysis/ScalarEvolution.h"
-#include "llvm/Analysis/TargetTransformInfo.h"
-#include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
-#include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include <functional>
 
 namespace llvm {
 
+class AssumptionCache;
+class BlockFrequencyInfo;
+class DemandedBits;
+class DominatorTree;
+class Function;
+class Loop;
+class LoopAccessInfo;
+class LoopInfo;
+class OptimizationRemarkEmitter;
+class ScalarEvolution;
+class TargetLibraryInfo;
+class TargetTransformInfo;
+
 /// The LoopVectorize Pass.
 struct LoopVectorizePass : public PassInfoMixin<LoopVectorizePass> {
   bool DisableUnrolling = false;
+
   /// If true, consider all loops for vectorization.
   /// If false, only loops that explicitly request vectorization are
   /// considered.
@@ -99,6 +101,7 @@ struct LoopVectorizePass : public PassInfoMixin<LoopVectorizePass> {
 
   bool processLoop(Loop *L);
 };
-}
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H
diff --git a/include/llvm/Transforms/Vectorize/SLPVectorizer.h b/include/llvm/Transforms/Vectorize/SLPVectorizer.h
index 6f258191e89eb..25f264c4722c4 100644
--- a/include/llvm/Transforms/Vectorize/SLPVectorizer.h
+++ b/include/llvm/Transforms/Vectorize/SLPVectorizer.h
@@ -1,4 +1,4 @@
-//===---- SLPVectorizer.h ---------------------------------------*- C++ -*-===//
+//===- SLPVectorizer.h ------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -19,30 +19,48 @@
 #ifndef LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
 #define LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
 
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/None.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
-#include "llvm/Analysis/AssumptionCache.h"
-#include "llvm/Analysis/DemandedBits.h"
-#include "llvm/Analysis/LoopInfo.h"
-#include "llvm/Analysis/OptimizationDiagnosticInfo.h"
-#include "llvm/Analysis/ScalarEvolution.h"
-#include "llvm/Analysis/TargetTransformInfo.h"
-#include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/ValueHandle.h"
 
 namespace llvm {
 
+class AssumptionCache;
+class BasicBlock;
+class CmpInst;
+class DataLayout;
+class DemandedBits;
+class DominatorTree;
+class Function;
+class InsertElementInst;
+class InsertValueInst;
+class Instruction;
+class LoopInfo;
+class OptimizationRemarkEmitter;
+class PHINode;
+class ScalarEvolution;
+class StoreInst;
+class TargetLibraryInfo;
+class TargetTransformInfo;
+class Value;
+
 /// A private "module" namespace for types and utilities used by this pass.
 /// These are implementation details and should not be used by clients.
 namespace slpvectorizer {
+
 class BoUpSLP;
-}
+
+} // end namespace slpvectorizer
 
 struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> {
-  typedef SmallVector<StoreInst *, 8> StoreList;
-  typedef MapVector<Value *, StoreList> StoreListMap;
-  typedef SmallVector<WeakTrackingVH, 8> WeakTrackingVHList;
-  typedef MapVector<Value *, WeakTrackingVHList> WeakTrackingVHListMap;
+  using StoreList = SmallVector<StoreInst *, 8>;
+  using StoreListMap = MapVector<Value *, StoreList>;
+  using WeakTrackingVHList = SmallVector<WeakTrackingVH, 8>;
+  using WeakTrackingVHListMap = MapVector<Value *, WeakTrackingVHList>;
 
   ScalarEvolution *SE = nullptr;
   TargetTransformInfo *TTI = nullptr;
@@ -78,14 +96,16 @@ private:
 
   /// \brief Try to vectorize a list of operands.
   /// \@param BuildVector A list of users to ignore for the purpose of
-  ///                     scheduling and that don't need extracting.
+  ///                     scheduling and cost estimation when NeedExtraction
+  ///                     is false.
   /// \returns true if a value was vectorized.
   bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R,
                           ArrayRef<Value *> BuildVector = None,
-                          bool AllowReorder = false);
+                          bool AllowReorder = false,
+                          bool NeedExtraction = false);
 
-  /// \brief Try to vectorize a chain that may start at the operands of \p V.
-  bool tryToVectorize(BinaryOperator *V, slpvectorizer::BoUpSLP &R);
+  /// \brief Try to vectorize a chain that may start at the operands of \p I.
+  bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R);
 
   /// \brief Vectorize the store instructions collected in Stores.
   bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R);
@@ -100,6 +120,22 @@ private:
                                 slpvectorizer::BoUpSLP &R,
                                 TargetTransformInfo *TTI);
 
+  /// Try to vectorize trees that start at insertvalue instructions.
+  bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB,
+                                slpvectorizer::BoUpSLP &R);
+
+  /// Try to vectorize trees that start at insertelement instructions.
+  bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB,
+                                  slpvectorizer::BoUpSLP &R);
+
+  /// Try to vectorize trees that start at compare instructions.
+  bool vectorizeCmpInst(CmpInst *CI, BasicBlock *BB, slpvectorizer::BoUpSLP &R);
+
+  /// Tries to vectorize constructs started from CmpInst, InsertValueInst or
+  /// InsertElementInst instructions.
+  bool vectorizeSimpleInstructions(SmallVectorImpl<WeakVH> &Instructions,
+                                   BasicBlock *BB, slpvectorizer::BoUpSLP &R);
+
   /// \brief Scan the basic block and look for patterns that are likely to start
   /// a vectorization chain.
   bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
@@ -115,6 +151,7 @@ private:
   /// The getelementptr instructions in a basic block organized by base pointer.
   WeakTrackingVHListMap GEPs;
 };
-}
+
+} // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H