Rebase: [NFC] Refactor sources to be buildable in shared mode

Summary:
Moves source files into separate components, and make explicit
component dependency on each other, so LLVM build system knows how to
build BOLT in BUILD_SHARED_LIBS=ON.

Please use the -c merge.renamelimit=230 git option when rebasing your
work on top of this change.

To achieve this, we create a new library to hold core IR files (most
classes beginning with Binary in their names), a new library to hold
Utils, some command line options shared across both RewriteInstance
and core IR files, a new library called Rewrite to hold most classes
concerned with running top-level functions coordinating the binary
rewriting process, and a new library called Profile to hold classes
dealing with profile reading and writing.

To remove the dependency from BinaryContext into X86-specific classes,
we do some refactoring on the BinaryContext constructor to receive a
reference to the specific backend directly from RewriteInstance. Then,
the dependency on X86 or AArch64-specific classes is transfered to the
Rewrite library. We can't have the Core library depend on targets
because targets depend on Core (which would create a cycle).

Files implementing the entry point of a tool are transferred to the
tools/ folder. All header files are transferred to the include/
folder. The src/ folder was renamed to lib/.

(cherry picked from FBD32746834)

5 files changed, 772 insertions, 0 deletions

diff --git a/bolt/tools/CMakeLists.txt b/bolt/tools/CMakeLists.txt
new file mode 100644
index 000000000000..2153a9b720b0
--- /dev/null
+++ b/bolt/tools/CMakeLists.txt
@@ -0,0 +1,2 @@
+add_subdirectory(driver)
+add_subdirectory(merge-fdata)
diff --git a/bolt/tools/driver/CMakeLists.txt b/bolt/tools/driver/CMakeLists.txt
new file mode 100644
index 000000000000..8ea0e5c2ee84
--- /dev/null
+++ b/bolt/tools/driver/CMakeLists.txt
@@ -0,0 +1,22 @@
+set(LLVM_LINK_COMPONENTS
+  ${LLVM_TARGETS_TO_BUILD}
+  BOLTProfile
+  BOLTRewrite
+  BOLTUtils
+  MC
+  Object
+  Support
+  )
+
+add_llvm_tool(llvm-bolt
+  llvm-bolt.cpp
+
+  DEPENDS
+  bolt_rt
+  )
+
+add_llvm_tool_symlink(perf2bolt llvm-bolt)
+add_llvm_tool_symlink(llvm-boltdiff llvm-bolt)
+add_llvm_tool_symlink(llvm-bolt-heatmap llvm-bolt)
+
+include_directories( ${BOLT_SOURCE_DIR}/lib )
diff --git a/bolt/tools/driver/llvm-bolt.cpp b/bolt/tools/driver/llvm-bolt.cpp
new file mode 100644
index 000000000000..6bafc2333c55
--- /dev/null
+++ b/bolt/tools/driver/llvm-bolt.cpp
@@ -0,0 +1,325 @@
+//===-- llvm-bolt.cpp - Feedback-directed layout optimizer ----------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This is a binary optimizer that will take 'perf' output and change
+// basic block layout for better performance (a.k.a. branch straightening),
+// plus some other optimizations that are better performed on a binary.
+//
+//===----------------------------------------------------------------------===//
+
+#include "bolt/Profile/DataAggregator.h"
+#include "bolt/Rewrite/MachORewriteInstance.h"
+#include "bolt/Rewrite/RewriteInstance.h"
+#include "bolt/Utils/CommandLineOpts.h"
+#include "llvm/MC/TargetRegistry.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/ManagedStatic.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/PrettyStackTrace.h"
+#include "llvm/Support/Signals.h"
+#include "llvm/Support/TargetSelect.h"
+
+#undef  DEBUG_TYPE
+#define DEBUG_TYPE "bolt"
+
+using namespace llvm;
+using namespace object;
+using namespace bolt;
+
+namespace opts {
+
+static cl::OptionCategory *BoltCategories[] = {&BoltCategory,
+                                               &BoltOptCategory,
+                                               &BoltRelocCategory,
+                                               &BoltInstrCategory,
+                                               &BoltOutputCategory};
+
+static cl::OptionCategory *BoltDiffCategories[] = {&BoltDiffCategory};
+
+static cl::OptionCategory *Perf2BoltCategories[] = {&AggregatorCategory,
+                                                    &BoltOutputCategory};
+
+static cl::opt<std::string>
+InputDataFilename("data",
+  cl::desc("<data file>"),
+  cl::Optional,
+  cl::cat(BoltCategory));
+
+static cl::alias
+BoltProfile("b",
+  cl::desc("alias for -data"),
+  cl::aliasopt(InputDataFilename),
+  cl::cat(BoltCategory));
+
+static cl::opt<std::string>
+InputDataFilename2("data2",
+  cl::desc("<data file>"),
+  cl::Optional,
+  cl::cat(BoltCategory));
+
+static cl::opt<std::string>
+InputFilename2(
+  cl::Positional,
+  cl::desc("<executable>"),
+  cl::Optional,
+  cl::cat(BoltDiffCategory));
+
+} // namespace opts
+
+static StringRef ToolName;
+
+static void report_error(StringRef Message, std::error_code EC) {
+  assert(EC);
+  errs() << ToolName << ": '" << Message << "': " << EC.message() << ".\n";
+  exit(1);
+}
+
+static void report_error(StringRef Message, Error E) {
+  assert(E);
+  errs() << ToolName << ": '" << Message << "': " << toString(std::move(E))
+         << ".\n";
+  exit(1);
+}
+
+static void printBoltRevision(llvm::raw_ostream &OS) {
+  OS << "BOLT revision " << BoltRevision << "\n";
+}
+
+void perf2boltMode(int argc, char **argv) {
+  cl::HideUnrelatedOptions(makeArrayRef(opts::Perf2BoltCategories));
+  cl::AddExtraVersionPrinter(printBoltRevision);
+  cl::ParseCommandLineOptions(
+      argc, argv,
+      "perf2bolt - BOLT data aggregator\n"
+      "\nEXAMPLE: perf2bolt -p=perf.data executable -o data.fdata\n");
+  if (opts::PerfData.empty()) {
+    errs() << ToolName << ": expected -perfdata=<filename> option.\n";
+    exit(1);
+  }
+  if (!opts::InputDataFilename.empty()) {
+    errs() << ToolName << ": unknown -data option.\n";
+    exit(1);
+  }
+  if (!sys::fs::exists(opts::PerfData))
+    report_error(opts::PerfData, errc::no_such_file_or_directory);
+  if (!DataAggregator::checkPerfDataMagic(opts::PerfData)) {
+    errs() << ToolName << ": '" << opts::PerfData
+           << "': expected valid perf.data file.\n";
+    exit(1);
+  }
+  if (opts::OutputFilename.empty()) {
+    errs() << ToolName << ": expected -o=<output file> option.\n";
+    exit(1);
+  }
+  opts::AggregateOnly = true;
+}
+
+void heatmapMode(int argc, char **argv) {
+  // Insert a fake subcommand if invoked via a command alias.
+  std::unique_ptr<char *[]> FakeArgv;
+  if (argc == 1 || strcmp(argv[1], "heatmap")) {
+    ++argc;
+    FakeArgv.reset(new char *[argc+1]);
+    FakeArgv[0] = argv[0];
+    FakeArgv[1] = const_cast<char *>("heatmap");
+    for (int I = 2; I < argc; ++I)
+      FakeArgv[I] = argv[I - 1];
+    FakeArgv[argc] = nullptr;
+    argv = FakeArgv.get();
+  }
+
+  cl::ParseCommandLineOptions(argc, argv, "");
+
+  if (!sys::fs::exists(opts::InputFilename))
+    report_error(opts::InputFilename, errc::no_such_file_or_directory);
+
+  if (opts::PerfData.empty()) {
+    errs() << ToolName << ": expected -perfdata=<filename> option.\n";
+    exit(1);
+  }
+
+  opts::HeatmapMode = true;
+  opts::AggregateOnly = true;
+}
+
+void boltDiffMode(int argc, char **argv) {
+  cl::HideUnrelatedOptions(makeArrayRef(opts::BoltDiffCategories));
+  cl::AddExtraVersionPrinter(printBoltRevision);
+  cl::ParseCommandLineOptions(
+      argc, argv,
+      "llvm-boltdiff - BOLT binary diff tool\n"
+      "\nEXAMPLE: llvm-boltdiff -data=a.fdata -data2=b.fdata exec1 exec2\n");
+  if (opts::InputDataFilename2.empty()) {
+    errs() << ToolName << ": expected -data2=<filename> option.\n";
+    exit(1);
+  }
+  if (opts::InputDataFilename.empty()) {
+    errs() << ToolName << ": expected -data=<filename> option.\n";
+    exit(1);
+  }
+  if (opts::InputFilename2.empty()) {
+    errs() << ToolName << ": expected second binary name.\n";
+    exit(1);
+  }
+  if (opts::InputFilename.empty()) {
+    errs() << ToolName << ": expected binary.\n";
+    exit(1);
+  }
+  opts::DiffOnly = true;
+}
+
+void boltMode(int argc, char **argv) {
+  cl::HideUnrelatedOptions(makeArrayRef(opts::BoltCategories));
+  // Register the target printer for --version.
+  cl::AddExtraVersionPrinter(printBoltRevision);
+  cl::AddExtraVersionPrinter(TargetRegistry::printRegisteredTargetsForVersion);
+
+  cl::ParseCommandLineOptions(argc, argv,
+                              "BOLT - Binary Optimization and Layout Tool\n");
+
+  if (opts::OutputFilename.empty()) {
+    errs() << ToolName << ": expected -o=<output file> option.\n";
+    exit(1);
+  }
+}
+
+std::string GetExecutablePath(const char *Argv0) {
+  SmallString<128> ExecutablePath(Argv0);
+  // Do a PATH lookup if Argv0 isn't a valid path.
+  if (!llvm::sys::fs::exists(ExecutablePath))
+    if (llvm::ErrorOr<std::string> P =
+            llvm::sys::findProgramByName(ExecutablePath))
+      ExecutablePath = *P;
+  return std::string(ExecutablePath.str());
+}
+
+int main(int argc, char **argv) {
+  // Print a stack trace if we signal out.
+  sys::PrintStackTraceOnErrorSignal(argv[0]);
+  PrettyStackTraceProgram X(argc, argv);
+
+  llvm_shutdown_obj Y;  // Call llvm_shutdown() on exit.
+
+  std::string ToolPath = GetExecutablePath(argv[0]);
+
+  // Initialize targets and assembly printers/parsers.
+  llvm::InitializeAllTargetInfos();
+  llvm::InitializeAllTargetMCs();
+  llvm::InitializeAllAsmParsers();
+  llvm::InitializeAllDisassemblers();
+
+  llvm::InitializeAllTargets();
+  llvm::InitializeAllAsmPrinters();
+
+  ToolName = argv[0];
+
+  // Pre-process subcommands.
+  if (argc > 1 && *argv[1] != '-') {
+    if (!strcmp(argv[1], "heatmap"))
+      opts::HeatmapMode = true;
+  }
+
+  if (llvm::sys::path::filename(ToolName) == "perf2bolt")
+    perf2boltMode(argc, argv);
+  else if (llvm::sys::path::filename(ToolName) == "llvm-boltdiff")
+    boltDiffMode(argc, argv);
+  else if (llvm::sys::path::filename(ToolName) == "llvm-bolt-heatmap" ||
+           opts::HeatmapMode)
+    heatmapMode(argc, argv);
+  else
+    boltMode(argc, argv);
+
+
+  if (!sys::fs::exists(opts::InputFilename))
+    report_error(opts::InputFilename, errc::no_such_file_or_directory);
+
+  // Attempt to open the binary.
+  if (!opts::DiffOnly) {
+    Expected<OwningBinary<Binary>> BinaryOrErr =
+        createBinary(opts::InputFilename);
+    if (Error E = BinaryOrErr.takeError())
+      report_error(opts::InputFilename, std::move(E));
+    Binary &Binary = *BinaryOrErr.get().getBinary();
+
+    if (auto *e = dyn_cast<ELFObjectFileBase>(&Binary)) {
+      RewriteInstance RI(e, argc, argv, ToolPath);
+      if (!opts::PerfData.empty()) {
+        if (!opts::AggregateOnly) {
+          errs() << ToolName
+            << ": WARNING: reading perf data directly is unsupported, please use "
+            "-aggregate-only or perf2bolt.\n!!! Proceed on your own risk. !!!\n";
+        }
+        if (Error E = RI.setProfile(opts::PerfData))
+          report_error(opts::PerfData, std::move(E));
+      }
+      if (!opts::InputDataFilename.empty()) {
+        if (Error E = RI.setProfile(opts::InputDataFilename))
+          report_error(opts::InputDataFilename, std::move(E));
+      }
+      if (opts::AggregateOnly && opts::PerfData.empty()) {
+        errs() << ToolName << ": missing required -perfdata option.\n";
+        exit(1);
+      }
+
+      RI.run();
+    } else if (auto *O = dyn_cast<MachOObjectFile>(&Binary)) {
+      MachORewriteInstance MachORI(O, ToolPath);
+
+      if (!opts::InputDataFilename.empty())
+        if (Error E = MachORI.setProfile(opts::InputDataFilename))
+          report_error(opts::InputDataFilename, std::move(E));
+
+      MachORI.run();
+    } else {
+      report_error(opts::InputFilename, object_error::invalid_file_type);
+    }
+
+    return EXIT_SUCCESS;
+  }
+
+  // Bolt-diff
+  Expected<OwningBinary<Binary>> BinaryOrErr1 =
+      createBinary(opts::InputFilename);
+  Expected<OwningBinary<Binary>> BinaryOrErr2 =
+      createBinary(opts::InputFilename2);
+  if (Error E = BinaryOrErr1.takeError())
+    report_error(opts::InputFilename, std::move(E));
+  if (Error E = BinaryOrErr2.takeError())
+    report_error(opts::InputFilename2, std::move(E));
+  Binary &Binary1 = *BinaryOrErr1.get().getBinary();
+  Binary &Binary2 = *BinaryOrErr2.get().getBinary();
+  if (auto *ELFObj1 = dyn_cast<ELFObjectFileBase>(&Binary1)) {
+    if (auto *ELFObj2 = dyn_cast<ELFObjectFileBase>(&Binary2)) {
+      RewriteInstance RI1(ELFObj1, argc, argv, ToolPath);
+      if (Error E = RI1.setProfile(opts::InputDataFilename))
+        report_error(opts::InputDataFilename, std::move(E));
+      RewriteInstance RI2(ELFObj2, argc, argv, ToolPath);
+      if (Error E = RI2.setProfile(opts::InputDataFilename2))
+        report_error(opts::InputDataFilename2, std::move(E));
+      outs() << "BOLT-DIFF: *** Analyzing binary 1: " << opts::InputFilename
+             << "\n";
+      outs() << "BOLT-DIFF: *** Binary 1 fdata:     " << opts::InputDataFilename
+             << "\n";
+      RI1.run();
+      outs() << "BOLT-DIFF: *** Analyzing binary 2: " << opts::InputFilename2
+             << "\n";
+      outs() << "BOLT-DIFF: *** Binary 2 fdata:     "
+             << opts::InputDataFilename2 << "\n";
+      RI2.run();
+      RI1.compare(RI2);
+    } else {
+      report_error(opts::InputFilename2, object_error::invalid_file_type);
+    }
+  } else {
+    report_error(opts::InputFilename, object_error::invalid_file_type);
+  }
+
+  return EXIT_SUCCESS;
+}
diff --git a/bolt/tools/merge-fdata/CMakeLists.txt b/bolt/tools/merge-fdata/CMakeLists.txt
new file mode 100644
index 000000000000..5acd7aa1263c
--- /dev/null
+++ b/bolt/tools/merge-fdata/CMakeLists.txt
@@ -0,0 +1,8 @@
+set(LLVM_LINK_COMPONENTS Support)
+
+add_llvm_tool(merge-fdata
+  merge-fdata.cpp
+
+  DEPENDS
+  intrinsics_gen
+)
diff --git a/bolt/tools/merge-fdata/merge-fdata.cpp b/bolt/tools/merge-fdata/merge-fdata.cpp
new file mode 100644
index 000000000000..0f4aa1fc4da8
--- /dev/null
+++ b/bolt/tools/merge-fdata/merge-fdata.cpp
@@ -0,0 +1,415 @@
+//===-- merge-fdata.cpp - Tool for merging profile in fdata format --------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// merge-fdata 1.fdata 2.fdata 3.fdata > merged.fdata
+//
+//===----------------------------------------------------------------------===//
+
+#include "bolt/Profile/ProfileYAMLMapping.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ManagedStatic.h"
+#include "llvm/Support/PrettyStackTrace.h"
+#include "llvm/Support/Signals.h"
+#include <unordered_map>
+
+using namespace llvm;
+using namespace llvm::yaml::bolt;
+
+namespace opts {
+
+cl::OptionCategory MergeFdataCategory("merge-fdata options");
+
+enum SortType : char {
+  ST_NONE,
+  ST_EXEC_COUNT,      /// Sort based on function execution count.
+  ST_TOTAL_BRANCHES,  /// Sort based on all branches in the function.
+};
+
+static cl::list<std::string>
+InputDataFilenames(
+  cl::Positional,
+  cl::CommaSeparated,
+  cl::desc("<fdata1> [<fdata2>]..."),
+  cl::OneOrMore,
+  cl::cat(MergeFdataCategory));
+
+static cl::opt<SortType>
+PrintFunctionList("print",
+  cl::desc("print the list of objects with count to stderr"),
+  cl::init(ST_NONE),
+  cl::values(clEnumValN(ST_NONE,
+      "none",
+      "do not print objects/functions"),
+    clEnumValN(ST_EXEC_COUNT,
+      "exec",
+      "print functions sorted by execution count"),
+    clEnumValN(ST_TOTAL_BRANCHES,
+      "branches",
+      "print functions sorted by total branch count")),
+  cl::cat(MergeFdataCategory));
+
+static cl::opt<bool>
+SuppressMergedDataOutput("q",
+  cl::desc("do not print merged data to stdout"),
+  cl::init(false),
+  cl::Optional,
+  cl::cat(MergeFdataCategory));
+
+} // namespace opts
+
+namespace {
+
+static StringRef ToolName;
+
+static void report_error(StringRef Message, std::error_code EC) {
+  assert(EC);
+  errs() << ToolName << ": '" << Message << "': " << EC.message() << ".\n";
+  exit(1);
+}
+
+static void report_error(Twine Message, StringRef CustomError) {
+  errs() << ToolName << ": '" << Message << "': " << CustomError << ".\n";
+  exit(1);
+}
+
+void mergeProfileHeaders(BinaryProfileHeader &MergedHeader,
+                         const BinaryProfileHeader &Header) {
+  if (MergedHeader.FileName.empty()) {
+    MergedHeader.FileName = Header.FileName;
+  }
+  if (!MergedHeader.FileName.empty() &&
+      MergedHeader.FileName != Header.FileName) {
+    errs() << "WARNING: merging profile from a binary for "
+           << Header.FileName << " into a profile for binary "
+           << MergedHeader.FileName << '\n';
+  }
+  if (MergedHeader.Id.empty()) {
+    MergedHeader.Id = Header.Id;
+  }
+  if (!MergedHeader.Id.empty() && (MergedHeader.Id != Header.Id)) {
+    errs() << "WARNING: build-ids in merged profiles do not match\n";
+  }
+
+  // Cannot merge samples profile with LBR profile.
+  if (!MergedHeader.Flags) {
+    MergedHeader.Flags = Header.Flags;
+  }
+  constexpr auto Mask = llvm::bolt::BinaryFunction::PF_LBR |
+                        llvm::bolt::BinaryFunction::PF_SAMPLE;
+  if ((MergedHeader.Flags & Mask) != (Header.Flags & Mask)) {
+    errs() << "ERROR: cannot merge LBR profile with non-LBR profile\n";
+    exit(1);
+  }
+  MergedHeader.Flags = MergedHeader.Flags | Header.Flags;
+
+  if (!Header.Origin.empty()) {
+    if (MergedHeader.Origin.empty()) {
+      MergedHeader.Origin = Header.Origin;
+    } else if (MergedHeader.Origin != Header.Origin) {
+      MergedHeader.Origin += "; " + Header.Origin;
+    }
+  }
+
+  if (MergedHeader.EventNames.empty()) {
+    MergedHeader.EventNames = Header.EventNames;
+  }
+  if (MergedHeader.EventNames != Header.EventNames) {
+    errs() << "WARNING: merging profiles with different sampling events\n";
+    MergedHeader.EventNames += "," + Header.EventNames;
+  }
+}
+
+void mergeBasicBlockProfile(BinaryBasicBlockProfile &MergedBB,
+                            BinaryBasicBlockProfile &&BB,
+                            const BinaryFunctionProfile &BF) {
+  // Verify that the blocks match.
+  if (BB.NumInstructions != MergedBB.NumInstructions)
+    report_error(BF.Name + " : BB #" + Twine(BB.Index),
+                 "number of instructions in block mismatch");
+  if (BB.Hash != MergedBB.Hash)
+    report_error(BF.Name + " : BB #" + Twine(BB.Index),
+                 "basic block hash mismatch");
+
+  // Update the execution count.
+  MergedBB.ExecCount += BB.ExecCount;
+
+  // Update the event count.
+  MergedBB.EventCount += BB.EventCount;
+
+  // Merge calls sites.
+  std::unordered_map<uint32_t, CallSiteInfo *> CSByOffset;
+  for (CallSiteInfo &CS : BB.CallSites)
+    CSByOffset.emplace(std::make_pair(CS.Offset, &CS));
+
+  for (CallSiteInfo &MergedCS : MergedBB.CallSites) {
+    auto CSI = CSByOffset.find(MergedCS.Offset);
+    if (CSI == CSByOffset.end())
+      continue;
+    yaml::bolt::CallSiteInfo &CS = *CSI->second;
+    if (CS != MergedCS)
+      continue;
+
+    MergedCS.Count += CS.Count;
+    MergedCS.Mispreds += CS.Mispreds;
+
+    CSByOffset.erase(CSI);
+  }
+
+  // Append the rest of call sites.
+  for (std::pair<const uint32_t, CallSiteInfo *> CSI : CSByOffset) {
+    MergedBB.CallSites.emplace_back(std::move(*CSI.second));
+  }
+
+  // Merge successor info.
+  std::vector<SuccessorInfo *> SIByIndex(BF.NumBasicBlocks);
+  for (SuccessorInfo &SI : BB.Successors) {
+    if (SI.Index >= BF.NumBasicBlocks)
+      report_error(BF.Name, "bad successor index");
+    SIByIndex[SI.Index] = &SI;
+  }
+  for (SuccessorInfo &MergedSI : MergedBB.Successors) {
+    if (!SIByIndex[MergedSI.Index])
+      continue;
+    SuccessorInfo &SI = *SIByIndex[MergedSI.Index];
+
+    MergedSI.Count += SI.Count;
+    MergedSI.Mispreds += SI.Mispreds;
+
+    SIByIndex[MergedSI.Index] = nullptr;
+  }
+  for (SuccessorInfo *SI : SIByIndex) {
+    if (SI) {
+      MergedBB.Successors.emplace_back(std::move(*SI));
+    }
+  }
+}
+
+void mergeFunctionProfile(BinaryFunctionProfile &MergedBF,
+                          BinaryFunctionProfile &&BF) {
+  // Validate that we are merging the correct function.
+  if (BF.NumBasicBlocks != MergedBF.NumBasicBlocks)
+    report_error(BF.Name, "number of basic blocks mismatch");
+  if (BF.Id != MergedBF.Id)
+    report_error(BF.Name, "ID mismatch");
+  if (BF.Hash != MergedBF.Hash)
+    report_error(BF.Name, "hash mismatch");
+
+  // Update the execution count.
+  MergedBF.ExecCount += BF.ExecCount;
+
+  // Merge basic blocks profile.
+  std::vector<BinaryBasicBlockProfile *> BlockByIndex(BF.NumBasicBlocks);
+  for (BinaryBasicBlockProfile &BB : BF.Blocks) {
+    if (BB.Index >= BF.NumBasicBlocks)
+      report_error(BF.Name + " : BB #" + Twine(BB.Index),
+                   "bad basic block index");
+    BlockByIndex[BB.Index] = &BB;
+  }
+  for (BinaryBasicBlockProfile &MergedBB : MergedBF.Blocks) {
+    if (!BlockByIndex[MergedBB.Index])
+      continue;
+    BinaryBasicBlockProfile &BB = *BlockByIndex[MergedBB.Index];
+
+    mergeBasicBlockProfile(MergedBB, std::move(BB), MergedBF);
+
+    // Ignore this block in the future.
+    BlockByIndex[MergedBB.Index] = nullptr;
+  }
+
+  // Append blocks unique to BF (i.e. those that are not in MergedBF).
+  for (BinaryBasicBlockProfile *BB : BlockByIndex) {
+    if (BB) {
+      MergedBF.Blocks.emplace_back(std::move(*BB));
+    }
+  }
+}
+
+bool isYAML(const StringRef Filename) {
+  ErrorOr<std::unique_ptr<MemoryBuffer>> MB =
+      MemoryBuffer::getFileOrSTDIN(Filename);
+  if (std::error_code EC = MB.getError())
+    report_error(Filename, EC);
+  StringRef Buffer = MB.get()->getBuffer();
+  if (Buffer.startswith("---\n"))
+    return true;
+  return false;
+}
+
+void mergeLegacyProfiles(const cl::list<std::string> &Filenames) {
+  errs() << "Using legacy profile format.\n";
+  bool BoltedCollection = false;
+  bool First = true;
+  for (const std::string &Filename : Filenames) {
+    if (isYAML(Filename))
+      report_error(Filename, "cannot mix YAML and legacy formats");
+    ErrorOr<std::unique_ptr<MemoryBuffer>> MB =
+        MemoryBuffer::getFileOrSTDIN(Filename);
+    if (std::error_code EC = MB.getError())
+      report_error(Filename, EC);
+    errs() << "Merging data from " << Filename << "...\n";
+
+    StringRef Buf = MB.get()->getBuffer();
+    // Check if the string "boltedcollection" is in the first line
+    if (Buf.startswith("boltedcollection\n")) {
+      if (!First && !BoltedCollection) {
+        report_error(
+            Filename,
+            "cannot mix profile collected in BOLT and non-BOLT deployments");
+      }
+      BoltedCollection = true;
+      if (!First)
+        Buf = Buf.drop_front(17);
+    } else {
+      if (BoltedCollection) {
+        report_error(
+            Filename,
+            "cannot mix profile collected in BOLT and non-BOLT deployments");
+      }
+    }
+
+    outs() << Buf;
+    First = false;
+  }
+  errs() << "Profile from " << Filenames.size() << " files merged.\n";
+}
+
+} // anonymous namespace
+
+int main(int argc, char **argv) {
+  // Print a stack trace if we signal out.
+  sys::PrintStackTraceOnErrorSignal(argv[0]);
+  PrettyStackTraceProgram X(argc, argv);
+
+  llvm_shutdown_obj Y;  // Call llvm_shutdown() on exit.
+
+  cl::HideUnrelatedOptions(opts::MergeFdataCategory);
+
+  cl::ParseCommandLineOptions(argc, argv,
+                              "merge multiple fdata into a single file");
+
+  ToolName = argv[0];
+
+  if (!isYAML(opts::InputDataFilenames.front())) {
+    mergeLegacyProfiles(opts::InputDataFilenames);
+    return 0;
+  }
+
+  // Merged header.
+  BinaryProfileHeader MergedHeader;
+  MergedHeader.Version = 1;
+
+  // Merged information for all functions.
+  StringMap<BinaryFunctionProfile> MergedBFs;
+
+  for (std::string &InputDataFilename : opts::InputDataFilenames) {
+    ErrorOr<std::unique_ptr<MemoryBuffer>> MB =
+        MemoryBuffer::getFileOrSTDIN(InputDataFilename);
+    if (std::error_code EC = MB.getError())
+      report_error(InputDataFilename, EC);
+    yaml::Input YamlInput(MB.get()->getBuffer());
+
+    errs() << "Merging data from " << InputDataFilename << "...\n";
+
+    BinaryProfile BP;
+    YamlInput >> BP;
+    if (YamlInput.error())
+      report_error(InputDataFilename, YamlInput.error());
+
+    // Sanity check.
+    if (BP.Header.Version != 1) {
+      errs() << "Unable to merge data from profile using version "
+             << BP.Header.Version << '\n';
+      exit(1);
+    }
+
+    // Merge the header.
+    mergeProfileHeaders(MergedHeader, BP.Header);
+
+    // Do the function merge.
+    for (BinaryFunctionProfile &BF : BP.Functions) {
+      if (!MergedBFs.count(BF.Name)) {
+        MergedBFs.insert(std::make_pair(BF.Name, BF));
+        continue;
+      }
+
+      BinaryFunctionProfile &MergedBF = MergedBFs.find(BF.Name)->second;
+      mergeFunctionProfile(MergedBF, std::move(BF));
+    }
+  }
+
+  if (!opts::SuppressMergedDataOutput) {
+    yaml::Output YamlOut(outs());
+
+    BinaryProfile MergedProfile;
+    MergedProfile.Header = MergedHeader;
+    MergedProfile.Functions.resize(MergedBFs.size());
+    std::transform(MergedBFs.begin(),
+                   MergedBFs.end(),
+                   MergedProfile.Functions.begin(),
+                   [] (StringMapEntry<BinaryFunctionProfile> &V) {
+                     return V.second;
+                   });
+
+    // For consistency, sort functions by their IDs.
+    std::sort(MergedProfile.Functions.begin(), MergedProfile.Functions.end(),
+              [] (const BinaryFunctionProfile &A,
+                  const BinaryFunctionProfile &B) {
+                return A.Id < B.Id;
+              });
+
+    YamlOut << MergedProfile;
+  }
+
+  errs() << "Data for " << MergedBFs.size()
+         << " unique objects successfully merged.\n";
+
+  if (opts::PrintFunctionList != opts::ST_NONE) {
+    // List of function names with execution count.
+    std::vector<std::pair<uint64_t, StringRef>> FunctionList(MergedBFs.size());
+    using CountFuncType =
+      std::function<std::pair<uint64_t, StringRef>(
+          const StringMapEntry<BinaryFunctionProfile> &)>;
+    CountFuncType ExecCountFunc =
+        [](const StringMapEntry<BinaryFunctionProfile> &V) {
+      return std::make_pair(V.second.ExecCount,
+                            StringRef(V.second.Name));
+    };
+    CountFuncType BranchCountFunc =
+        [](const StringMapEntry<BinaryFunctionProfile> &V) {
+      // Return total branch count.
+      uint64_t BranchCount = 0;
+      for (const BinaryBasicBlockProfile &BI : V.second.Blocks) {
+        for (const SuccessorInfo &SI : BI.Successors) {
+          BranchCount += SI.Count;
+        }
+      }
+      return std::make_pair(BranchCount,
+                            StringRef(V.second.Name));
+    };
+
+    CountFuncType CountFunc = (opts::PrintFunctionList == opts::ST_EXEC_COUNT)
+       ? ExecCountFunc
+       : BranchCountFunc;
+    std::transform(MergedBFs.begin(),
+                   MergedBFs.end(),
+                   FunctionList.begin(),
+                   CountFunc);
+    std::stable_sort(FunctionList.rbegin(), FunctionList.rend());
+    errs() << "Functions sorted by "
+           << (opts::PrintFunctionList == opts::ST_EXEC_COUNT
+                ? "execution"
+                : "total branch")
+           << " count:\n";
+    for (std::pair<uint64_t, StringRef> &FI : FunctionList) {
+      errs() << FI.second << " : " << FI.first << '\n';
+    }
+  }
+
+  return 0;
+}