vendor/llvm/llvm-release_39-r276489

18 files changed, 883 insertions, 53 deletions

diff --git a/include/llvm/Transforms/IPO/ConstantMerge.h b/include/llvm/Transforms/IPO/ConstantMerge.h
new file mode 100644
index 0000000000000..1d4da43f6a7bb
--- /dev/null
+++ b/include/llvm/Transforms/IPO/ConstantMerge.h
@@ -0,0 +1,35 @@
+//===- ConstantMerge.h - Merge duplicate global constants -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the interface to a pass that merges duplicate global
+// constants together into a single constant that is shared.  This is useful
+// because some passes (ie TraceValues) insert a lot of string constants into
+// the program, regardless of whether or not an existing string is available.
+//
+// Algorithm: ConstantMerge is designed to build up a map of available constants
+// and eliminate duplicates when it is initialized.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_CONSTANTMERGE_H
+#define LLVM_TRANSFORMS_IPO_CONSTANTMERGE_H
+
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+/// A pass that merges duplicate global constants into a single constant.
+class ConstantMergePass : public PassInfoMixin<ConstantMergePass> {
+public:
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
+};
+}
+
+#endif // LLVM_TRANSFORMS_IPO_CONSTANTMERGE_H
diff --git a/include/llvm/Transforms/IPO/CrossDSOCFI.h b/include/llvm/Transforms/IPO/CrossDSOCFI.h
new file mode 100644
index 0000000000000..409604a7f3302
--- /dev/null
+++ b/include/llvm/Transforms/IPO/CrossDSOCFI.h
@@ -0,0 +1,28 @@
+//===-- CrossDSOCFI.cpp - Externalize this module's CFI checks --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass exports all llvm.bitset's found in the module in the form of a
+// __cfi_check function, which can be used to verify cross-DSO call targets.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_CROSSDSOCFI_H
+#define LLVM_TRANSFORMS_IPO_CROSSDSOCFI_H
+
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+class CrossDSOCFIPass : public PassInfoMixin<CrossDSOCFIPass> {
+public:
+  PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM);
+};
+}
+#endif // LLVM_TRANSFORMS_IPO_CROSSDSOCFI_H
+
diff --git a/include/llvm/Transforms/IPO/DeadArgumentElimination.h b/include/llvm/Transforms/IPO/DeadArgumentElimination.h
new file mode 100644
index 0000000000000..e179afa956f6e
--- /dev/null
+++ b/include/llvm/Transforms/IPO/DeadArgumentElimination.h
@@ -0,0 +1,133 @@
+//===- DeadArgumentElimination.h - Eliminate Dead Args ----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass deletes dead arguments from internal functions.  Dead argument
+// elimination removes arguments which are directly dead, as well as arguments
+// only passed into function calls as dead arguments of other functions.  This
+// pass also deletes dead return values in a similar way.
+//
+// This pass is often useful as a cleanup pass to run after aggressive
+// interprocedural passes, which add possibly-dead arguments or return values.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
+#define LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
+
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+
+#include <map>
+#include <set>
+#include <string>
+
+namespace llvm {
+
+/// Eliminate dead arguments (and return values) from functions.
+class DeadArgumentEliminationPass
+    : public PassInfoMixin<DeadArgumentEliminationPass> {
+public:
+  /// Struct that represents (part of) either a return value or a function
+  /// 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;
+
+    /// 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);
+    }
+
+    /// Make RetOrArg comparable, so we can easily iterate the multimap.
+    bool operator==(const RetOrArg &O) const {
+      return F == O.F && Idx == O.Idx && IsArg == O.IsArg;
+    }
+
+    std::string getDescription() const {
+      return (Twine(IsArg ? "Argument #" : "Return value #") + Twine(Idx) +
+              " of function " + F->getName())
+          .str();
+    }
+  };
+
+  /// Liveness enum - During our initial pass over the program, we determine
+  /// that things are either alive or maybe alive. We don't mark anything
+  /// explicitly dead (even if we know they are), since anything not alive
+  /// with no registered uses (in Uses) will never be marked alive and will
+  /// thus become dead in the end.
+  enum Liveness { Live, MaybeLive };
+
+  /// 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;
+  /// 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.
+  /// For example (indices are left out for clarity):
+  ///  - Uses[ret F] = ret G
+  ///    This means that F calls G, and F returns the value returned by G.
+  ///  - Uses[arg F] = ret G
+  ///    This means that some function calls G and passes its result as an
+  ///    argument to F.
+  ///  - Uses[ret F] = arg F
+  ///    This means that F returns one of its own arguments.
+  ///  - Uses[arg F] = arg G
+  ///    This means that G calls F and passes one of its own (G's) arguments
+  ///    directly to F.
+  UseMap Uses;
+
+  typedef std::set<RetOrArg> LiveSet;
+  typedef std::set<const Function *> LiveFuncSet;
+
+  /// 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;
+
+  /// 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,
+                     unsigned RetValNum = -1U);
+  Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses);
+
+  void SurveyFunction(const Function &F);
+  void MarkValue(const RetOrArg &RA, Liveness L,
+                 const UseVector &MaybeLiveUses);
+  void MarkLive(const RetOrArg &RA);
+  void MarkLive(const Function &F);
+  void PropagateLiveness(const RetOrArg &RA);
+  bool RemoveDeadStuffFromFunction(Function *F);
+  bool DeleteDeadVarargs(Function &Fn);
+  bool RemoveDeadArgumentsFromCallers(Function &Fn);
+};
+}
+
+#endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
diff --git a/include/llvm/Transforms/IPO/ElimAvailExtern.h b/include/llvm/Transforms/IPO/ElimAvailExtern.h
new file mode 100644
index 0000000000000..88a0e9bd8ce0f
--- /dev/null
+++ b/include/llvm/Transforms/IPO/ElimAvailExtern.h
@@ -0,0 +1,31 @@
+//===- ElimAvailExtern.h - Optimize Global Variables ------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This transform is designed to eliminate available external global
+// definitions from the program, turning them into declarations.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_ELIMAVAILEXTERN_H
+#define LLVM_TRANSFORMS_IPO_ELIMAVAILEXTERN_H
+
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+/// A pass that transforms external global definitions into declarations.
+class EliminateAvailableExternallyPass
+    : public PassInfoMixin<EliminateAvailableExternallyPass> {
+public:
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
+};
+}
+
+#endif // LLVM_TRANSFORMS_IPO_ELIMAVAILEXTERN_H
diff --git a/include/llvm/Transforms/IPO/ForceFunctionAttrs.h b/include/llvm/Transforms/IPO/ForceFunctionAttrs.h
index 0ff4afe79b0cc..ff8a6546f0591 100644
--- a/include/llvm/Transforms/IPO/ForceFunctionAttrs.h
+++ b/include/llvm/Transforms/IPO/ForceFunctionAttrs.h
@@ -21,10 +21,8 @@ namespace llvm {
 
 /// Pass which forces specific function attributes into the IR, primarily as
 /// a debugging tool.
-class ForceFunctionAttrsPass {
-public:
-  static StringRef name() { return "ForceFunctionAttrsPass"; }
-  PreservedAnalyses run(Module &M);
+struct ForceFunctionAttrsPass : PassInfoMixin<ForceFunctionAttrsPass> {
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
 };
 
 /// Create a legacy pass manager instance of a pass to force function attrs.
diff --git a/include/llvm/Transforms/IPO/FunctionAttrs.h b/include/llvm/Transforms/IPO/FunctionAttrs.h
new file mode 100644
index 0000000000000..c44cc43fc0f6a
--- /dev/null
+++ b/include/llvm/Transforms/IPO/FunctionAttrs.h
@@ -0,0 +1,57 @@
+//===-- FunctionAttrs.h - Compute function attrs --------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// Provides passes for computing function attributes based on interprocedural
+/// analyses.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H
+#define LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H
+
+#include "llvm/Analysis/LazyCallGraph.h"
+#include "llvm/Analysis/CGSCCPassManager.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+/// Computes function attributes in post-order over the call graph.
+///
+/// By operating in post-order, this pass computes precise attributes for
+/// called functions prior to processsing their callers. This "bottom-up"
+/// approach allows powerful interprocedural inference of function attributes
+/// like memory access patterns, etc. It can discover functions that do not
+/// access memory, or only read memory, and give them the readnone/readonly
+/// attribute. It also discovers function arguments that are not captured by
+/// the function and marks them with the nocapture attribute.
+struct PostOrderFunctionAttrsPass : PassInfoMixin<PostOrderFunctionAttrsPass> {
+  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM);
+};
+
+/// Create a legacy pass manager instance of a pass to compute function attrs
+/// in post-order.
+Pass *createPostOrderFunctionAttrsLegacyPass();
+
+/// A pass to do RPO deduction and propagation of function attributes.
+///
+/// This pass provides a general RPO or "top down" propagation of
+/// function attributes. For a few (rare) cases, we can deduce significantly
+/// more about function attributes by working in RPO, so this pass
+/// provides the compliment to the post-order pass above where the majority of
+/// deduction is performed.
+// FIXME: Currently there is no RPO CGSCC pass structure to slide into and so
+// this is a boring module pass, but eventually it should be an RPO CGSCC pass
+// when such infrastructure is available.
+class ReversePostOrderFunctionAttrsPass
+    : public PassInfoMixin<ReversePostOrderFunctionAttrsPass> {
+public:
+  PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM);
+};
+}
+
+#endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H
diff --git a/include/llvm/Transforms/IPO/FunctionImport.h b/include/llvm/Transforms/IPO/FunctionImport.h
index d7707790a0179..ba5db2b5c7391 100644
--- a/include/llvm/Transforms/IPO/FunctionImport.h
+++ b/include/llvm/Transforms/IPO/FunctionImport.h
@@ -11,33 +11,113 @@
 #define LLVM_FUNCTIONIMPORT_H
 
 #include "llvm/ADT/StringMap.h"
+#include "llvm/IR/GlobalValue.h"
+#include "llvm/IR/ModuleSummaryIndex.h"
+
 #include <functional>
+#include <map>
+#include <unordered_set>
+#include <utility>
 
 namespace llvm {
 class LLVMContext;
+class GlobalValueSummary;
 class Module;
-class FunctionInfoIndex;
 
 /// The function importer is automatically importing function from other modules
 /// based on the provided summary informations.
 class FunctionImporter {
+public:
+  /// Set of functions to import from a source module. Each entry is a map
+  /// 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;
 
-  /// The summaries index used to trigger importing.
-  const FunctionInfoIndex &Index;
+  /// 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;
 
-  /// Factory function to load a Module for a given identifier
-  std::function<std::unique_ptr<Module>(StringRef Identifier)> ModuleLoader;
+  /// The set contains an entry for every global value the module exports.
+  typedef std::unordered_set<GlobalValue::GUID> ExportSetTy;
 
-public:
   /// Create a Function Importer.
   FunctionImporter(
-      const FunctionInfoIndex &Index,
+      const ModuleSummaryIndex &Index,
       std::function<std::unique_ptr<Module>(StringRef Identifier)> ModuleLoader)
-      : Index(Index), ModuleLoader(ModuleLoader) {}
+      : Index(Index), ModuleLoader(std::move(ModuleLoader)) {}
+
+  /// Import functions in Module \p M based on the supplied import list.
+  /// \p ForceImportReferencedDiscardableSymbols will set the ModuleLinker in
+  /// a mode where referenced discarable symbols in the source modules will be
+  /// imported as well even if they are not present in the ImportList.
+  bool importFunctions(Module &M, const ImportMapTy &ImportList,
+                       bool ForceImportReferencedDiscardableSymbols = false);
 
-  /// Import functions in Module \p M based on the summary informations.
-  bool importFunctions(Module &M);
+private:
+  /// The summaries index used to trigger importing.
+  const ModuleSummaryIndex &Index;
+
+  /// Factory function to load a Module for a given identifier
+  std::function<std::unique_ptr<Module>(StringRef Identifier)> ModuleLoader;
 };
+
+/// Compute all the imports and exports for every module in the Index.
+///
+/// \p ModuleToDefinedGVSummaries contains for each Module a map
+/// (GUID -> Summary) for every global defined in the module.
+///
+/// \p ImportLists will be populated with an entry for every Module we are
+/// importing into. This entry is itself a map that can be passed to
+/// FunctionImporter::importFunctions() above (see description there).
+///
+/// \p ExportLists contains for each Module the set of globals (GUID) that will
+/// be imported by another module, or referenced by such a function. I.e. this
+/// is the set of globals that need to be promoted/renamed appropriately.
+void ComputeCrossModuleImport(
+    const ModuleSummaryIndex &Index,
+    const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
+    StringMap<FunctionImporter::ImportMapTy> &ImportLists,
+    StringMap<FunctionImporter::ExportSetTy> &ExportLists);
+
+/// Compute all the imports for the given module using the Index.
+///
+/// \p ImportList will be populated with a map that can be passed to
+/// FunctionImporter::importFunctions() above (see description there).
+void ComputeCrossModuleImportForModule(
+    StringRef ModulePath, const ModuleSummaryIndex &Index,
+    FunctionImporter::ImportMapTy &ImportList);
+
+/// Compute the set of summaries needed for a ThinLTO backend compilation of
+/// \p ModulePath.
+//
+/// This includes summaries from that module (in case any global summary based
+/// optimizations were recorded) and from any definitions in other modules that
+/// should be imported.
+//
+/// \p ModuleToSummariesForIndex will be populated with the needed summaries
+/// from each required module path. Use a std::map instead of StringMap to get
+/// stable order for bitcode emission.
+void gatherImportedSummariesForModule(
+    StringRef ModulePath,
+    const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
+    const StringMap<FunctionImporter::ImportMapTy> &ImportLists,
+    std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex);
+
+std::error_code
+EmitImportsFiles(StringRef ModulePath, StringRef OutputFilename,
+                 const StringMap<FunctionImporter::ImportMapTy> &ImportLists);
+
+/// Resolve WeakForLinker values in \p TheModule based on the information
+/// recorded in the summaries during global summary-based analysis.
+void thinLTOResolveWeakForLinkerModule(Module &TheModule,
+                                       const GVSummaryMapTy &DefinedGlobals);
+
+/// Internalize \p TheModule based on the information recorded in the summaries
+/// during global summary-based analysis.
+void thinLTOInternalizeModule(Module &TheModule,
+                              const GVSummaryMapTy &DefinedGlobals);
 }
 
 #endif // LLVM_FUNCTIONIMPORT_H
diff --git a/include/llvm/Transforms/IPO/GlobalDCE.h b/include/llvm/Transforms/IPO/GlobalDCE.h
new file mode 100644
index 0000000000000..57e174c2a37fe
--- /dev/null
+++ b/include/llvm/Transforms/IPO/GlobalDCE.h
@@ -0,0 +1,46 @@
+//===-- GlobalDCE.h - DCE unreachable internal functions ------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This transform is designed to eliminate unreachable internal globals from the
+// program.  It uses an aggressive algorithm, searching out globals that are
+// known to be alive.  After it finds all of the globals which are needed, it
+// deletes whatever is left over.  This allows it to delete recursive chunks of
+// the program which are unreachable.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_GLOBALDCE_H
+#define LLVM_TRANSFORMS_IPO_GLOBALDCE_H
+
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+#include <unordered_map>
+
+namespace llvm {
+
+/// Pass to remove unused function declarations.
+class GlobalDCEPass : public PassInfoMixin<GlobalDCEPass> {
+public:
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
+
+private:
+  SmallPtrSet<GlobalValue*, 32> AliveGlobals;
+  SmallPtrSet<Constant *, 8> SeenConstants;
+  std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
+
+  /// Mark the specific global value as needed, and
+  /// recursively mark anything that it uses as also needed.
+  void GlobalIsNeeded(GlobalValue *GV);
+  void MarkUsedGlobalsAsNeeded(Constant *C);
+  bool RemoveUnusedGlobalValue(GlobalValue &GV);
+};
+
+}
+
+#endif // LLVM_TRANSFORMS_IPO_GLOBALDCE_H
diff --git a/include/llvm/Transforms/IPO/GlobalOpt.h b/include/llvm/Transforms/IPO/GlobalOpt.h
new file mode 100644
index 0000000000000..5a25a6db43909
--- /dev/null
+++ b/include/llvm/Transforms/IPO/GlobalOpt.h
@@ -0,0 +1,32 @@
+//===- GlobalOpt.h - Optimize Global Variables ------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass transforms simple global variables that never have their address
+// taken.  If obviously true, it marks read/write globals as constant, deletes
+// variables only stored to, etc.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_GLOBALOPT_H
+#define LLVM_TRANSFORMS_IPO_GLOBALOPT_H
+
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+/// Optimize globals that never have their address taken.
+class GlobalOptPass : public PassInfoMixin<GlobalOptPass> {
+public:
+  PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM);
+};
+
+}
+
+#endif // LLVM_TRANSFORMS_IPO_GLOBALOPT_H
diff --git a/include/llvm/Transforms/IPO/InferFunctionAttrs.h b/include/llvm/Transforms/IPO/InferFunctionAttrs.h
index 80afc02c62ae8..f5cbf9eb06137 100644
--- a/include/llvm/Transforms/IPO/InferFunctionAttrs.h
+++ b/include/llvm/Transforms/IPO/InferFunctionAttrs.h
@@ -23,10 +23,8 @@ namespace llvm {
 
 /// A pass which infers function attributes from the names and signatures of
 /// function declarations in a module.
-class InferFunctionAttrsPass {
-public:
-  static StringRef name() { return "InferFunctionAttrsPass"; }
-  PreservedAnalyses run(Module &M, AnalysisManager<Module> *AM);
+struct InferFunctionAttrsPass : PassInfoMixin<InferFunctionAttrsPass> {
+  PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM);
 };
 
 /// Create a legacy pass manager instance of a pass to infer function
diff --git a/include/llvm/Transforms/IPO/InlinerPass.h b/include/llvm/Transforms/IPO/InlinerPass.h
index 58ef0cbbfb5d0..59e10608a9ba2 100644
--- a/include/llvm/Transforms/IPO/InlinerPass.h
+++ b/include/llvm/Transforms/IPO/InlinerPass.h
@@ -24,6 +24,7 @@ class AssumptionCacheTracker;
 class CallSite;
 class DataLayout;
 class InlineCost;
+class ProfileSummaryInfo;
 template <class PtrType, unsigned SmallSize> class SmallPtrSet;
 
 /// Inliner - This class contains all of the helper code which is used to
@@ -31,7 +32,7 @@ template <class PtrType, unsigned SmallSize> class SmallPtrSet;
 ///
 struct Inliner : public CallGraphSCCPass {
   explicit Inliner(char &ID);
-  explicit Inliner(char &ID, int Threshold, bool InsertLifetime);
+  explicit Inliner(char &ID, bool InsertLifetime);
 
   /// getAnalysisUsage - For this class, we declare that we require and preserve
   /// the call graph.  If the derived class implements this method, it should
@@ -47,18 +48,6 @@ struct Inliner : public CallGraphSCCPass {
   // processing to avoid breaking the SCC traversal.
   bool doFinalization(CallGraph &CG) override;
 
-  /// This method returns the value specified by the -inline-threshold value,
-  /// specified on the command line.  This is typically not directly needed.
-  ///
-  unsigned getInlineThreshold() const { return InlineThreshold; }
-
-  /// Calculate the inline threshold for given Caller. This threshold is lower
-  /// if the caller is marked with OptimizeForSize and -inline-threshold is not
-  /// given on the comand line. It is higher if the callee is marked with the
-  /// inlinehint attribute.
-  ///
-  unsigned getInlineThreshold(CallSite CS) const;
-
   /// getInlineCost - This method must be implemented by the subclass to
   /// determine the cost of inlining the specified call site.  If the cost
   /// returned is greater than the current inline threshold, the call site is
@@ -74,19 +63,30 @@ struct Inliner : public CallGraphSCCPass {
   /// deal with that subset of the functions.
   bool removeDeadFunctions(CallGraph &CG, bool AlwaysInlineOnly = false);
 
-private:
-  // InlineThreshold - Cache the value here for easy access.
-  unsigned InlineThreshold;
+  /// This function performs the main work of the pass.  The default
+  /// of Inlinter::runOnSCC() calls skipSCC() before calling this method, but
+  /// derived classes which cannot be skipped can override that method and
+  /// call this function unconditionally.
+  bool inlineCalls(CallGraphSCC &SCC);
 
+private:
   // InsertLifetime - Insert @llvm.lifetime intrinsics.
   bool InsertLifetime;
 
   /// shouldInline - Return true if the inliner should attempt to
   /// inline at the given CallSite.
   bool shouldInline(CallSite CS);
+  /// Return true if inlining of CS can block the caller from being
+  /// inlined which is proved to be more beneficial. \p IC is the
+  /// estimated inline cost associated with callsite \p CS.
+  /// \p TotalAltCost will be set to the estimated cost of inlining the caller
+  /// if \p CS is suppressed for inlining.
+  bool shouldBeDeferred(Function *Caller, CallSite CS, InlineCost IC,
+                        int &TotalAltCost);
 
 protected:
   AssumptionCacheTracker *ACT;
+  ProfileSummaryInfo *PSI;
 };
 
 } // End llvm namespace
diff --git a/include/llvm/Transforms/IPO/Internalize.h b/include/llvm/Transforms/IPO/Internalize.h
new file mode 100644
index 0000000000000..ba1b06877d3a5
--- /dev/null
+++ b/include/llvm/Transforms/IPO/Internalize.h
@@ -0,0 +1,79 @@
+//====- Internalize.h - Internalization API ---------------------*- C++ -*-===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass loops over all of the functions and variables in the input module.
+// If the function or variable does not need to be preserved according to the
+// client supplied callback, it is marked as internal.
+//
+// This transformation would not be legal in a regular compilation, but it gets
+// extra information from the linker about what is safe.
+//
+// For example: Internalizing a function with external linkage. Only if we are
+// told it is only used from within this module, it is safe to do it.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_INTERNALIZE_H
+#define LLVM_TRANSFORMS_IPO_INTERNALIZE_H
+
+#include "llvm/ADT/StringSet.h"
+#include "llvm/IR/GlobalValue.h"
+#include "llvm/IR/PassManager.h"
+#include <functional>
+#include <set>
+
+namespace llvm {
+class Module;
+class CallGraph;
+
+/// A pass that internalizes all functions and variables other than those that
+/// must be preserved according to \c MustPreserveGV.
+class InternalizePass : public PassInfoMixin<InternalizePass> {
+  /// Client supplied callback to control wheter a symbol must be preserved.
+  const std::function<bool(const GlobalValue &)> MustPreserveGV;
+  /// Set of symbols private to the compiler that this pass should not touch.
+  StringSet<> AlwaysPreserved;
+
+  /// Return false if we're allowed to internalize this GV.
+  bool shouldPreserveGV(const GlobalValue &GV);
+  /// Internalize GV if it is possible to do so, i.e. it is not externally
+  /// visible and is not a member of an externally visible comdat.
+  bool maybeInternalize(GlobalValue &GV,
+                        const std::set<const Comdat *> &ExternalComdats);
+  /// If GV is part of a comdat and is externally visible, keep track of its
+  /// comdat so that we don't internalize any of its members.
+  void checkComdatVisibility(GlobalValue &GV,
+                             std::set<const Comdat *> &ExternalComdats);
+
+public:
+  InternalizePass();
+  InternalizePass(std::function<bool(const GlobalValue &)> MustPreserveGV)
+      : MustPreserveGV(std::move(MustPreserveGV)) {}
+
+  /// Run the internalizer on \p TheModule, returns true if any changes was
+  /// made.
+  ///
+  /// If the CallGraph \p CG is supplied, it will be updated when
+  /// internalizing a function (by removing any edge from the "external node")
+  bool internalizeModule(Module &TheModule, CallGraph *CG = nullptr);
+
+  PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM);
+};
+
+/// Helper function to internalize functions and variables in a Module.
+inline bool
+internalizeModule(Module &TheModule,
+                  std::function<bool(const GlobalValue &)> MustPreserveGV,
+                  CallGraph *CG = nullptr) {
+  return InternalizePass(std::move(MustPreserveGV))
+      .internalizeModule(TheModule, CG);
+}
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_IPO_INTERNALIZE_H
diff --git a/include/llvm/Transforms/IPO/LowerBitSets.h b/include/llvm/Transforms/IPO/LowerTypeTests.h
index e5fb7b98fcb3d..93d4fb94e2c4b 100644
--- a/include/llvm/Transforms/IPO/LowerBitSets.h
+++ b/include/llvm/Transforms/IPO/LowerTypeTests.h
@@ -1,4 +1,4 @@
-//===- LowerBitSets.h - Bitset lowering pass --------------------*- C++ -*-===//
+//===- LowerTypeTests.h - type metadata lowering pass -----------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -7,18 +7,21 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// This file defines parts of the bitset lowering pass implementation that may
-// be usefully unit tested.
+// This file defines parts of the type test lowering pass implementation that
+// may be usefully unit tested.
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_TRANSFORMS_IPO_LOWERBITSETS_H
-#define LLVM_TRANSFORMS_IPO_LOWERBITSETS_H
+#ifndef LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H
+#define LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
 
-#include <stdint.h>
+#include <cstdint>
+#include <cstring>
 #include <limits>
 #include <set>
 #include <vector>
@@ -30,6 +33,8 @@ class GlobalObject;
 class Value;
 class raw_ostream;
 
+namespace lowertypetests {
+
 struct BitSetInfo {
   // The indices of the set bits in the bitset.
   std::set<uint64_t> Bits;
@@ -196,6 +201,13 @@ struct ByteArrayBuilder {
                 uint64_t &AllocByteOffset, uint8_t &AllocMask);
 };
 
-} // namespace llvm
+} // end namespace lowertypetests
+
+class LowerTypeTestsPass : public PassInfoMixin<LowerTypeTestsPass> {
+public:
+  PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM);
+};
+
+} // end namespace llvm
 
-#endif
+#endif // LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H
diff --git a/include/llvm/Transforms/IPO/PartialInlining.h b/include/llvm/Transforms/IPO/PartialInlining.h
new file mode 100644
index 0000000000000..48eb1e30a1914
--- /dev/null
+++ b/include/llvm/Transforms/IPO/PartialInlining.h
@@ -0,0 +1,32 @@
+//===- PartialInlining.h - Inline parts of functions --------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass performs partial inlining, typically by inlining an if statement
+// that surrounds the body of the function.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_PARTIALINLINING_H
+#define LLVM_TRANSFORMS_IPO_PARTIALINLINING_H
+
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+/// Pass to remove unused function declarations.
+class PartialInlinerPass : public PassInfoMixin<PartialInlinerPass> {
+public:
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
+
+private:
+  Function *unswitchFunction(Function *F);
+};
+}
+#endif // LLVM_TRANSFORMS_IPO_PARTIALINLINING_H
diff --git a/include/llvm/Transforms/IPO/PassManagerBuilder.h b/include/llvm/Transforms/IPO/PassManagerBuilder.h
index a4e7bce8ef4ae..4f483deeefe5d 100644
--- a/include/llvm/Transforms/IPO/PassManagerBuilder.h
+++ b/include/llvm/Transforms/IPO/PassManagerBuilder.h
@@ -15,11 +15,13 @@
 #ifndef LLVM_TRANSFORMS_IPO_PASSMANAGERBUILDER_H
 #define LLVM_TRANSFORMS_IPO_PASSMANAGERBUILDER_H
 
+#include <functional>
 #include <memory>
+#include <string>
 #include <vector>
 
 namespace llvm {
-class FunctionInfoIndex;
+class ModuleSummaryIndex;
 class Pass;
 class TargetLibraryInfoImpl;
 class TargetMachine;
@@ -58,8 +60,9 @@ class PassManagerBuilder {
 public:
   /// Extensions are passed the builder itself (so they can see how it is
   /// configured) as well as the pass manager to add stuff to.
-  typedef void (*ExtensionFn)(const PassManagerBuilder &Builder,
-                              legacy::PassManagerBase &PM);
+  typedef std::function<void(const PassManagerBuilder &Builder,
+                             legacy::PassManagerBase &PM)>
+      ExtensionFn;
   enum ExtensionPointTy {
     /// EP_EarlyAsPossible - This extension point allows adding passes before
     /// any other transformations, allowing them to see the code as it is coming
@@ -116,8 +119,8 @@ public:
   /// added to the per-module passes.
   Pass *Inliner;
 
-  /// The function summary index to use for function importing.
-  const FunctionInfoIndex *FunctionIndex;
+  /// The module summary index to use for function importing.
+  const ModuleSummaryIndex *ModuleSummary;
 
   bool DisableTailCalls;
   bool DisableUnitAtATime;
@@ -132,10 +135,17 @@ public:
   bool VerifyOutput;
   bool MergeFunctions;
   bool PrepareForLTO;
+  bool PrepareForThinLTO;
+  bool PerformThinLTO;
+
+  /// Profile data file name that the instrumentation will be written to.
+  std::string PGOInstrGen;
+  /// Path of the profile data file.
+  std::string PGOInstrUse;
 
 private:
   /// ExtensionList - This is list of all of the extensions that are registered.
-  std::vector<std::pair<ExtensionPointTy, ExtensionFn> > Extensions;
+  std::vector<std::pair<ExtensionPointTy, ExtensionFn>> Extensions;
 
 public:
   PassManagerBuilder();
@@ -152,6 +162,9 @@ private:
   void addInitialAliasAnalysisPasses(legacy::PassManagerBase &PM) const;
   void addLTOOptimizationPasses(legacy::PassManagerBase &PM);
   void addLateLTOOptimizationPasses(legacy::PassManagerBase &PM);
+  void addPGOInstrPasses(legacy::PassManagerBase &MPM);
+  void addFunctionSimplificationPasses(legacy::PassManagerBase &MPM);
+  void addInstructionCombiningPass(legacy::PassManagerBase &MPM) const;
 
 public:
   /// populateFunctionPassManager - This fills in the function pass manager,
@@ -162,6 +175,7 @@ public:
   /// populateModulePassManager - This sets up the primary pass manager.
   void populateModulePassManager(legacy::PassManagerBase &MPM);
   void populateLTOPassManager(legacy::PassManagerBase &PM);
+  void populateThinLTOPassManager(legacy::PassManagerBase &PM);
 };
 
 /// Registers a function for adding a standard set of passes.  This should be
@@ -171,7 +185,7 @@ public:
 struct RegisterStandardPasses {
   RegisterStandardPasses(PassManagerBuilder::ExtensionPointTy Ty,
                          PassManagerBuilder::ExtensionFn Fn) {
-    PassManagerBuilder::addGlobalExtension(Ty, Fn);
+    PassManagerBuilder::addGlobalExtension(Ty, std::move(Fn));
   }
 };
 
diff --git a/include/llvm/Transforms/IPO/SCCP.h b/include/llvm/Transforms/IPO/SCCP.h
new file mode 100644
index 0000000000000..fab731342144c
--- /dev/null
+++ b/include/llvm/Transforms/IPO/SCCP.h
@@ -0,0 +1,34 @@
+//===- SCCP.h - Sparse Conditional Constant Propagation ---------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass implements  interprocedural sparse conditional constant
+// propagation and merging.
+//
+// Specifically, this:
+//   * Assumes values are constant unless proven otherwise
+//   * Assumes BasicBlocks are dead unless proven otherwise
+//   * Proves values to be constant, and replaces them with constants
+//   * Proves conditional branches to be unconditional
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_SCCP_H
+#define LLVM_TRANSFORMS_IPO_SCCP_H
+
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+/// Pass to perform interprocedural constant propagation.
+class IPSCCPPass : public PassInfoMixin<IPSCCPPass> {
+public:
+  PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM);
+};
+}
+#endif // LLVM_TRANSFORMS_IPO_SCCP_H
diff --git a/include/llvm/Transforms/IPO/StripDeadPrototypes.h b/include/llvm/Transforms/IPO/StripDeadPrototypes.h
index 9dddd12871c42..5a05cd75c9d55 100644
--- a/include/llvm/Transforms/IPO/StripDeadPrototypes.h
+++ b/include/llvm/Transforms/IPO/StripDeadPrototypes.h
@@ -23,10 +23,8 @@
 namespace llvm {
 
 /// Pass to remove unused function declarations.
-class StripDeadPrototypesPass {
-public:
-  static StringRef name() { return "StripDeadPrototypesPass"; }
-  PreservedAnalyses run(Module &M);
+struct StripDeadPrototypesPass : PassInfoMixin<StripDeadPrototypesPass> {
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
 };
 
 }
diff --git a/include/llvm/Transforms/IPO/WholeProgramDevirt.h b/include/llvm/Transforms/IPO/WholeProgramDevirt.h
new file mode 100644
index 0000000000000..2bd20c95702c6
--- /dev/null
+++ b/include/llvm/Transforms/IPO/WholeProgramDevirt.h
@@ -0,0 +1,223 @@
+//===- WholeProgramDevirt.h - Whole-program devirt pass ---------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines parts of the whole-program devirtualization pass
+// implementation that may be usefully unit tested.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
+#define LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
+
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+#include <cassert>
+#include <cstdint>
+#include <utility>
+#include <vector>
+
+namespace llvm {
+
+template <typename T> class ArrayRef;
+template <typename T> class MutableArrayRef;
+class Function;
+class GlobalVariable;
+
+namespace wholeprogramdevirt {
+
+// A bit vector that keeps track of which bits are used. We use this to
+// pack constant values compactly before and after each virtual table.
+struct AccumBitVector {
+  std::vector<uint8_t> Bytes;
+
+  // Bits in BytesUsed[I] are 1 if matching bit in Bytes[I] is used, 0 if not.
+  std::vector<uint8_t> BytesUsed;
+
+  std::pair<uint8_t *, uint8_t *> getPtrToData(uint64_t Pos, uint8_t Size) {
+    if (Bytes.size() < Pos + Size) {
+      Bytes.resize(Pos + Size);
+      BytesUsed.resize(Pos + Size);
+    }
+    return std::make_pair(Bytes.data() + Pos, BytesUsed.data() + Pos);
+  }
+
+  // Set little-endian value Val with size Size at bit position Pos,
+  // and mark bytes as used.
+  void setLE(uint64_t Pos, uint64_t Val, uint8_t Size) {
+    assert(Pos % 8 == 0);
+    auto DataUsed = getPtrToData(Pos / 8, Size);
+    for (unsigned I = 0; I != Size; ++I) {
+      DataUsed.first[I] = Val >> (I * 8);
+      assert(!DataUsed.second[I]);
+      DataUsed.second[I] = 0xff;
+    }
+  }
+
+  // Set big-endian value Val with size Size at bit position Pos,
+  // and mark bytes as used.
+  void setBE(uint64_t Pos, uint64_t Val, uint8_t Size) {
+    assert(Pos % 8 == 0);
+    auto DataUsed = getPtrToData(Pos / 8, Size);
+    for (unsigned I = 0; I != Size; ++I) {
+      DataUsed.first[Size - I - 1] = Val >> (I * 8);
+      assert(!DataUsed.second[Size - I - 1]);
+      DataUsed.second[Size - I - 1] = 0xff;
+    }
+  }
+
+  // Set bit at bit position Pos to b and mark bit as used.
+  void setBit(uint64_t Pos, bool b) {
+    auto DataUsed = getPtrToData(Pos / 8, 1);
+    if (b)
+      *DataUsed.first |= 1 << (Pos % 8);
+    assert(!(*DataUsed.second & (1 << Pos % 8)));
+    *DataUsed.second |= 1 << (Pos % 8);
+  }
+};
+
+// The bits that will be stored before and after a particular vtable.
+struct VTableBits {
+  // The vtable global.
+  GlobalVariable *GV;
+
+  // Cache of the vtable's size in bytes.
+  uint64_t ObjectSize = 0;
+
+  // The bit vector that will be laid out before the vtable. Note that these
+  // bytes are stored in reverse order until the globals are rebuilt. This means
+  // that any values in the array must be stored using the opposite endianness
+  // from the target.
+  AccumBitVector Before;
+
+  // The bit vector that will be laid out after the vtable.
+  AccumBitVector After;
+};
+
+// Information about a member of a particular type identifier.
+struct TypeMemberInfo {
+  // The VTableBits for the vtable.
+  VTableBits *Bits;
+
+  // The offset in bytes from the start of the vtable (i.e. the address point).
+  uint64_t Offset;
+
+  bool operator<(const TypeMemberInfo &other) const {
+    return Bits < other.Bits || (Bits == other.Bits && Offset < other.Offset);
+  }
+};
+
+// A virtual call target, i.e. an entry in a particular vtable.
+struct VirtualCallTarget {
+  VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM);
+
+  // For testing only.
+  VirtualCallTarget(const TypeMemberInfo *TM, bool IsBigEndian)
+      : Fn(nullptr), TM(TM), IsBigEndian(IsBigEndian) {}
+
+  // The function stored in the vtable.
+  Function *Fn;
+
+  // A pointer to the type identifier member through which the pointer to Fn is
+  // accessed.
+  const TypeMemberInfo *TM;
+
+  // When doing virtual constant propagation, this stores the return value for
+  // the function when passed the currently considered argument list.
+  uint64_t RetVal;
+
+  // Whether the target is big endian.
+  bool IsBigEndian;
+
+  // The minimum byte offset before the address point. This covers the bytes in
+  // the vtable object before the address point (e.g. RTTI, access-to-top,
+  // vtables for other base classes) and is equal to the offset from the start
+  // of the vtable object to the address point.
+  uint64_t minBeforeBytes() const { return TM->Offset; }
+
+  // The minimum byte offset after the address point. This covers the bytes in
+  // the vtable object after the address point (e.g. the vtable for the current
+  // class and any later base classes) and is equal to the size of the vtable
+  // object minus the offset from the start of the vtable object to the address
+  // point.
+  uint64_t minAfterBytes() const { return TM->Bits->ObjectSize - TM->Offset; }
+
+  // The number of bytes allocated (for the vtable plus the byte array) before
+  // the address point.
+  uint64_t allocatedBeforeBytes() const {
+    return minBeforeBytes() + TM->Bits->Before.Bytes.size();
+  }
+
+  // The number of bytes allocated (for the vtable plus the byte array) after
+  // the address point.
+  uint64_t allocatedAfterBytes() const {
+    return minAfterBytes() + TM->Bits->After.Bytes.size();
+  }
+
+  // Set the bit at position Pos before the address point to RetVal.
+  void setBeforeBit(uint64_t Pos) {
+    assert(Pos >= 8 * minBeforeBytes());
+    TM->Bits->Before.setBit(Pos - 8 * minBeforeBytes(), RetVal);
+  }
+
+  // Set the bit at position Pos after the address point to RetVal.
+  void setAfterBit(uint64_t Pos) {
+    assert(Pos >= 8 * minAfterBytes());
+    TM->Bits->After.setBit(Pos - 8 * minAfterBytes(), RetVal);
+  }
+
+  // Set the bytes at position Pos before the address point to RetVal.
+  // Because the bytes in Before are stored in reverse order, we use the
+  // opposite endianness to the target.
+  void setBeforeBytes(uint64_t Pos, uint8_t Size) {
+    assert(Pos >= 8 * minBeforeBytes());
+    if (IsBigEndian)
+      TM->Bits->Before.setLE(Pos - 8 * minBeforeBytes(), RetVal, Size);
+    else
+      TM->Bits->Before.setBE(Pos - 8 * minBeforeBytes(), RetVal, Size);
+  }
+
+  // Set the bytes at position Pos after the address point to RetVal.
+  void setAfterBytes(uint64_t Pos, uint8_t Size) {
+    assert(Pos >= 8 * minAfterBytes());
+    if (IsBigEndian)
+      TM->Bits->After.setBE(Pos - 8 * minAfterBytes(), RetVal, Size);
+    else
+      TM->Bits->After.setLE(Pos - 8 * minAfterBytes(), RetVal, Size);
+  }
+};
+
+// Find the minimum offset that we may store a value of size Size bits at. If
+// IsAfter is set, look for an offset before the object, otherwise look for an
+// offset after the object.
+uint64_t findLowestOffset(ArrayRef<VirtualCallTarget> Targets, bool IsAfter,
+                          uint64_t Size);
+
+// Set the stored value in each of Targets to VirtualCallTarget::RetVal at the
+// given allocation offset before the vtable address. Stores the computed
+// byte/bit offset to OffsetByte/OffsetBit.
+void setBeforeReturnValues(MutableArrayRef<VirtualCallTarget> Targets,
+                           uint64_t AllocBefore, unsigned BitWidth,
+                           int64_t &OffsetByte, uint64_t &OffsetBit);
+
+// Set the stored value in each of Targets to VirtualCallTarget::RetVal at the
+// given allocation offset after the vtable address. Stores the computed
+// byte/bit offset to OffsetByte/OffsetBit.
+void setAfterReturnValues(MutableArrayRef<VirtualCallTarget> Targets,
+                          uint64_t AllocAfter, unsigned BitWidth,
+                          int64_t &OffsetByte, uint64_t &OffsetBit);
+
+} // end namespace wholeprogramdevirt
+
+struct WholeProgramDevirtPass : public PassInfoMixin<WholeProgramDevirtPass> {
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H