[ThinLTO] Compute synthetic function entry count

Summary:
This patch computes the synthetic function entry count on the whole
program callgraph (based on module summary) and writes the entry counts
to the summary. After function importing, this count gets attached to
the IR as metadata. Since it adds a new field to the summary, this bumps
up the version.

Reviewers: tejohnson

Subscribers: mehdi_amini, inglorion, llvm-commits

Differential Revision: https://reviews.llvm.org/D43521

llvm-svn: 349076

4 files changed, 90 insertions, 0 deletions

diff --git a/llvm/lib/LTO/CMakeLists.txt b/llvm/lib/LTO/CMakeLists.txt
index 73b5662d4bc..1730df665d8 100644
--- a/llvm/lib/LTO/CMakeLists.txt
+++ b/llvm/lib/LTO/CMakeLists.txt
@@ -4,6 +4,7 @@ add_llvm_library(LLVMLTO
   LTOBackend.cpp
   LTOModule.cpp
   LTOCodeGenerator.cpp
+  SummaryBasedOptimizations.cpp
   UpdateCompilerUsed.cpp
   ThinLTOCodeGenerator.cpp
 
diff --git a/llvm/lib/LTO/LTO.cpp b/llvm/lib/LTO/LTO.cpp
index c99d44d1c90..08924fb92dd 100644
--- a/llvm/lib/LTO/LTO.cpp
+++ b/llvm/lib/LTO/LTO.cpp
@@ -25,6 +25,7 @@
 #include "llvm/IR/Mangler.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/LTO/LTOBackend.h"
+#include "llvm/LTO/SummaryBasedOptimizations.h"
 #include "llvm/Linker/IRMover.h"
 #include "llvm/Object/IRObjectFile.h"
 #include "llvm/Support/Error.h"
@@ -42,6 +43,7 @@
 #include "llvm/Target/TargetOptions.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
+#include "llvm/Transforms/Utils/FunctionImportUtils.h"
 #include "llvm/Transforms/Utils/SplitModule.h"
 
 #include <set>
@@ -1170,6 +1172,9 @@ Error LTO::runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache) {
     if (!ModuleToDefinedGVSummaries.count(Mod.first))
       ModuleToDefinedGVSummaries.try_emplace(Mod.first);
 
+  // Synthesize entry counts for functions in the CombinedIndex.
+  computeSyntheticCounts(ThinLTO.CombinedIndex);
+
   StringMap<FunctionImporter::ImportMapTy> ImportLists(
       ThinLTO.ModuleMap.size());
   StringMap<FunctionImporter::ExportSetTy> ExportLists(
diff --git a/llvm/lib/LTO/SummaryBasedOptimizations.cpp b/llvm/lib/LTO/SummaryBasedOptimizations.cpp
new file mode 100644
index 00000000000..8b1abb78462
--- /dev/null
+++ b/llvm/lib/LTO/SummaryBasedOptimizations.cpp
@@ -0,0 +1,80 @@
+//==-SummaryBasedOptimizations.cpp - Optimizations based on ThinLTO summary-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements optimizations that are based on the module summaries.
+// These optimizations are performed during the thinlink phase of the
+// compilation.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/LTO/SummaryBasedOptimizations.h"
+#include "llvm/Analysis/SyntheticCountsUtils.h"
+#include "llvm/IR/ModuleSummaryIndex.h"
+
+using namespace llvm;
+
+cl::opt<bool> ThinLTOSynthesizeEntryCounts(
+    "thinlto-synthesize-entry-counts", cl::init(false), cl::Hidden,
+    cl::desc("Synthesize entry counts based on the summary"));
+
+extern cl::opt<int> InitialSyntheticCount;
+
+static void initializeCounts(ModuleSummaryIndex &Index) {
+  auto Root = Index.calculateCallGraphRoot();
+  // Root is a fake node. All its successors are the actual roots of the
+  // callgraph.
+  // FIXME: This initializes the entry counts of only the root nodes. This makes
+  // sense when compiling a binary with ThinLTO, but for libraries any of the
+  // non-root nodes could be called from outside.
+  for (auto &C : Root.calls()) {
+    auto &V = C.first;
+    for (auto &GVS : V.getSummaryList()) {
+      auto S = GVS.get()->getBaseObject();
+      auto *F = cast<FunctionSummary>(S);
+      F->setEntryCount(InitialSyntheticCount);
+    }
+  }
+}
+
+void llvm::computeSyntheticCounts(ModuleSummaryIndex &Index) {
+  if (!ThinLTOSynthesizeEntryCounts)
+    return;
+
+  using Scaled64 = ScaledNumber<uint64_t>;
+  initializeCounts(Index);
+  auto GetCallSiteRelFreq = [](FunctionSummary::EdgeTy &Edge) {
+    return Scaled64(Edge.second.RelBlockFreq, -CalleeInfo::ScaleShift);
+  };
+  auto GetEntryCount = [](ValueInfo V) {
+    if (V.getSummaryList().size()) {
+      auto S = V.getSummaryList().front().get()->getBaseObject();
+      auto *F = cast<FunctionSummary>(S);
+      return F->entryCount();
+    } else {
+      return UINT64_C(0);
+    }
+  };
+  auto AddToEntryCount = [](ValueInfo V, uint64_t New) {
+    if (!V.getSummaryList().size())
+      return;
+    for (auto &GVS : V.getSummaryList()) {
+      auto S = GVS.get()->getBaseObject();
+      auto *F = cast<FunctionSummary>(S);
+      F->setEntryCount(SaturatingAdd(F->entryCount(), New));
+    }
+  };
+
+  // After initializing the counts in initializeCounts above, the counts have to
+  // be propagated across the combined callgraph.
+  // SyntheticCountsUtils::propagate takes care of this propagation on any
+  // callgraph that specialized GraphTraits.
+  SyntheticCountsUtils<ModuleSummaryIndex *>::propagate(
+      &Index, GetCallSiteRelFreq, GetEntryCount, AddToEntryCount);
+  Index.setHasSyntheticEntryCounts();
+}
diff --git a/llvm/lib/LTO/ThinLTOCodeGenerator.cpp b/llvm/lib/LTO/ThinLTOCodeGenerator.cpp
index fe0f5b7d4cb..d9ec68fe3eb 100644
--- a/llvm/lib/LTO/ThinLTOCodeGenerator.cpp
+++ b/llvm/lib/LTO/ThinLTOCodeGenerator.cpp
@@ -33,6 +33,7 @@
 #include "llvm/IR/Verifier.h"
 #include "llvm/IRReader/IRReader.h"
 #include "llvm/LTO/LTO.h"
+#include "llvm/LTO/SummaryBasedOptimizations.h"
 #include "llvm/MC/SubtargetFeature.h"
 #include "llvm/Object/IRObjectFile.h"
 #include "llvm/Support/CachePruning.h"
@@ -883,6 +884,9 @@ void ThinLTOCodeGenerator::run() {
   // Compute "dead" symbols, we don't want to import/export these!
   computeDeadSymbolsInIndex(*Index, GUIDPreservedSymbols);
 
+  // Synthesize entry counts for functions in the combined index.
+  computeSyntheticCounts(*Index);
+
   // Collect the import/export lists for all modules from the call-graph in the
   // combined index.
   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);