Add a pass to generate synthetic function entry counts.

[eraman]

Summary

This pass synthesizes function entry counts by traversing the callgraph
and using the relative block frequencies of the callsites. The intended
use of these counts is in inlining to determine hot/cold callsites in
the absence of profile information.

The pass is split into two files with the code that propagates the
counts in a callgraph in a Utils file. I plan to add support for
propagation in the thinlto link phase and the propagation code will be
shared and hence this split. I did not add support to the old PM since
hot callsite determination in inlining is not possible in old PM
(although we could use hot callee heuristic with synthetic counts in the
old PM it is not worth the effort tuning it)

[davidxl]

include/llvm/Analysis/SyntheticCountsUtils.h

28

add documentation comments here.

include/llvm/IR/Function.h

256

Is it better to let getEntryCount to take an optional flag to indicate 'is_synthetic'? The implementation of these two are mostly the same.

lib/Transforms/IPO/SyntheticCountsPropagation.cpp

49

We should probably differentiate functions with cold attributes and set them with lower initial count.

71

This should be restricted to local functions not address escaped. If the local function is only called indirectly, setting its initial count to zero can make it look too cold. For address exposed ones, the initial count should be handled similarly to global functions.

[eraman]

include/llvm/Analysis/SyntheticCountsUtils.h

28

I have the documentation comments next to the implementation in the cpp file.

include/llvm/IR/Function.h

256

I actually intended to remove this but this slipped in. I have a follow up patch that makes EntryCount a class and make the getEntryCount return it. Using a boolean for synthetic feels brittle. Shall I remove this get method?

[eraman]

Address review comments.

[davidxl]

include/llvm/IR/Function.h

256

The new interface that returns EntryCount seems a better approach. Yes, if you can unify the interfaces, this one should be removed. You can do it in two steps -- one takes the boolean flag, and then improved with a follow up patch.

lib/Analysis/SyntheticCountsUtils.cpp

50

Nit: callsites that call into the SCC come first.

64

PropagatedCounts --> ExtraSCCEntryCountFromCycles ? or just ExtraSCCEntryCounts?

Also modify the comments to say:

1. first update the global count of nodes with SCC using cyclic edges first.
2. the update is done in two steps ..

67

Weight --> RelativeFreq

It is confusing to see Weight multiplied by Count

lib/Transforms/IPO/SyntheticCountsPropagation.cpp

106

Call it CallSiteRelFreq may make the code more readable.

[eraman]

include/llvm/IR/Function.h

256

This patch doesn't read the synthetic entry count and hence I am just removing the getSyntheticEntryCount from this. I will leave the boolean on the setEntryCount and in the next patch add an EntryCount class.

lib/Analysis/SyntheticCountsUtils.cpp

64

I have modified the comments along the lines of what you say. I have renamed the variable to AdditionalCounts - I prefer this to your other suggestions.

[eraman]

Address David's comments.

[davidxl]

lgtm

lib/Transforms/IPO/SyntheticCountsPropagation.cpp

61

make it zero perhaps?

[eraman]

lib/Transforms/IPO/SyntheticCountsPropagation.cpp

61

I have no strong opinion, but I expect the default values to change after we make the inliner use these synthetic counts and tune the inliner. So I'll leave it as 5 for now.

include/llvm/Analysis/SyntheticCountsUtils.h

+//===- SyntheticCountsUtils.h - utilities for count propagation--*- 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 utilities for synthetic counts propagation.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_SYNTHETIC_COUNTS_UTILS_H
+#define LLVM_ANALYSIS_SYNTHETIC_COUNTS_UTILS_H
+
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/Support/ScaledNumber.h"
+
+namespace llvm {
+
+class CallGraph;
+class Function;
+
+using Scaled64 = ScaledNumber<uint64_t>;
+void propagateSyntheticCounts(
+    const CallGraph &CG, function_ref<Scaled64(CallSite CS)> GetCallSiteWeight,
+    function_ref<uint64_t(Function *F)> GetCount,
+    function_ref<void(Function *F, uint64_t)> AddToCount);
+} // namespace llvm
+
+#endif

include/llvm/IR/Function.h

public:
   void removeFnAttr(StringRef Kind) {
     setAttributes(getAttributes().removeAttribute(
         getContext(), AttributeList::FunctionIndex, Kind));
   }
 
   /// \brief Set the entry count for this function.
   ///
   /// Entry count is the number of times this function was executed based on
-  /// pgo data. \p Imports points to a set of GUIDs that needs to be imported
-  /// by the function for sample PGO, to enable the same inlines as the
-  /// profiled optimized binary.
-  void setEntryCount(uint64_t Count,
+  /// pgo data. \p Synthetic indicates the count is synthesized by analysis and
+  /// not from a profile run. \p Imports points to a set of GUIDs that needs to
+  /// be imported by the function for sample PGO, to enable the same inlines as
+  /// the profiled optimized binary.
+  void setEntryCount(uint64_t Count, bool Synthetic = false,
                      const DenseSet<GlobalValue::GUID> *Imports = nullptr);
 
   /// \brief Get the entry count for this function.
   ///
   /// Entry count is the number of times the function was executed based on
   /// pgo data.
   Optional<uint64_t> getEntryCount() const;
 
+  /// \brief Get the synthetic entry count for this function.
+  ///
+  /// Entry count is an estimate of the number of times the function
+  /// will execute.
+  Optional<uint64_t> getSyntheticEntryCount() const;
+
   /// Return true if the function is annotated with profile data.
   ///
   /// Presence of entry counts from a profile run implies the function has
   /// profile annotations.
   bool hasProfileData() const { return getEntryCount().hasValue(); }
 
   /// Returns the set of GUIDs that needs to be imported to the function for
   /// sample PGO, to enable the same inlines as the profiled optimized binary.

include/llvm/IR/MDBuilder.h

public:
   MDNode *createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight);
 
   /// \brief Return metadata containing a number of branch weights.
   MDNode *createBranchWeights(ArrayRef<uint32_t> Weights);
 
   /// Return metadata specifying that a branch or switch is unpredictable.
   MDNode *createUnpredictable();
 
-  /// Return metadata containing the entry \p Count for a function, and the
+  /// Return metadata containing the entry \p Count for a function, a boolean
+  /// \Synthetic indicating whether the counts were synthetized, and the
   /// GUIDs stored in \p Imports that need to be imported for sample PGO, to
   /// enable the same inlines as the profiled optimized binary
-  MDNode *createFunctionEntryCount(uint64_t Count,
+  MDNode *createFunctionEntryCount(uint64_t Count, bool Synthetic,
                                    const DenseSet<GlobalValue::GUID> *Imports);
 
   /// Return metadata containing the section prefix for a function.
   MDNode *createFunctionSectionPrefix(StringRef Prefix);
 
   //===------------------------------------------------------------------===//
   // Range metadata.
   //===------------------------------------------------------------------===//

include/llvm/Transforms/IPO/SyntheticCountsPropagation.h

+#ifndef LLVM_TRANSFORMS_IPO_SYNTHETIC_COUNTS_PROPAGATION_H
+#define LLVM_TRANSFORMS_IPO_SYNTHETIC_COUNTS_PROPAGATION_H
+
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Support/ScaledNumber.h"
+
+namespace llvm {
+class Function;
+class Module;
+
+class SyntheticCountsPropagation
+    : public PassInfoMixin<SyntheticCountsPropagation> {
+public:
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &MAM);
+};
+} // namespace llvm
+#endif

lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   PtrUseVisitor.cpp
   RegionInfo.cpp
   RegionPass.cpp
   RegionPrinter.cpp
   ScalarEvolution.cpp
   ScalarEvolutionAliasAnalysis.cpp
   ScalarEvolutionExpander.cpp
   ScalarEvolutionNormalization.cpp
+  SyntheticCountsUtils.cpp
   TargetLibraryInfo.cpp
   TargetTransformInfo.cpp
   Trace.cpp
   TypeBasedAliasAnalysis.cpp
   TypeMetadataUtils.cpp
   ScopedNoAliasAA.cpp
   ValueLattice.cpp
   ValueLatticeUtils.cpp

lib/Analysis/SyntheticCountsUtils.cpp

+//===--- SyntheticCountsUtils.cpp - synthetic counts propagation utils ---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines utilities for propagating synthetic counts.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/SyntheticCountsUtils.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Analysis/CallGraph.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instructions.h"
+
+using namespace llvm;
+
+// Given a set of functions in an SCC, propagate entry counts to functions
+// called by the SCC.
+static void
+propagateFromSCC(const SmallPtrSetImpl<Function *> &SCCFunctions,
+                 function_ref<Scaled64(CallSite CS)> GetCallSiteWeight,
+                 function_ref<uint64_t(Function *F)> GetCount,
+                 function_ref<void(Function *F, uint64_t)> AddToCount) {
+
+  SmallVector<CallSite, 16> CallSites;
+
+  // Gather all callsites in the SCC.
+  auto GatherCallSites = [&]() {
+    for (auto *F : SCCFunctions) {
+      assert(F && !F->isDeclaration());
+      for (auto &I : instructions(F)) {
+        if (auto CS = CallSite(&I)) {
+          CallSites.push_back(CS);
+        }
+      }
+    }
+  };
+
+  GatherCallSites();
+
+  // Partition callsites so that those in the same SCC come first.
+  auto Mid = partition(CallSites, [&](CallSite &CS) {
+    auto *Callee = CS.getCalledFunction();
+    if (Callee)
+      return SCCFunctions.count(Callee);
+    // FIXME: Use the !callees metadata to propagate counts through indirect
+    // calls.
+    return 0U;
+  });
+
+  // For callsites to the same SCC, first propagate the weights before updating
+  // the weights for the functions in the SCC. Update the counts only after
+  // computing the values for all the functions. This ensures that the order of
+  // traversal of functions within the SCC doesn't affect the computation.
+  DenseMap<Function *, uint64_t> PropagatedCounts;
+  for (auto It = CallSites.begin(); It != Mid; It++) {
+    auto &CS = *It;
+    auto Weight = GetCallSiteWeight(CS);
+    Function *Callee = CS.getCalledFunction();
+    Function *Caller = CS.getCaller();
+    Weight *= Scaled64(GetCount(Caller), 0);
+    uint64_t ExtraCount = Weight.toInt<uint64_t>();
+    PropagatedCounts[Callee] += ExtraCount;
+  }
+
+  // Update the counts for the functions in the SCC.
+  for (auto &Entry : PropagatedCounts)
+    AddToCount(Entry.first, Entry.second);
+
+  // Now update the counts for functions not in SCC.
+  for (auto It = Mid; It != CallSites.end(); It++) {
+    auto &CS = *It;
+    auto Weight = GetCallSiteWeight(CS);
+    Function *Callee = CS.getCalledFunction();
+    Function *Caller = CS.getCaller();
+    Weight *= Scaled64(GetCount(Caller), 0);
+    AddToCount(Callee, Weight.toInt<uint64_t>());
+  }
+}
+
+/// Propgate synthetic entry counts on a callgraph.
+///
+/// This performs a reverse post-order traversal of the callgraph SCC. For each
+/// SCC, it first propagates the entry counts to the functions within the SCC
+/// through call edges and updates them in one shot. Then the entry counts are
+/// propagated to functions outside the SCC.
+void llvm::propagateSyntheticCounts(
+    const CallGraph &CG, function_ref<Scaled64(CallSite CS)> GetCallSiteWeight,
+    function_ref<uint64_t(Function *F)> GetCount,
+    function_ref<void(Function *F, uint64_t)> AddToCount) {
+
+  SmallVector<SmallPtrSet<Function *, 8>, 16> SCCs;
+  for (auto I = scc_begin(&CG); !I.isAtEnd(); ++I) {
+    auto SCC = *I;
+
+    SmallPtrSet<Function *, 8> SCCFunctions;
+    for (auto *Node : SCC) {
+      Function *F = Node->getFunction();
+      if (F && !F->isDeclaration()) {
+        SCCFunctions.insert(F);
+      }
+    }
+    SCCs.push_back(SCCFunctions);
+  }
+
+  for (auto &SCCFunctions : reverse(SCCs))
+    propagateFromSCC(SCCFunctions, GetCallSiteWeight, GetCount, AddToCount);
+}

lib/IR/Function.cpp

 void Function::setValueSubclassDataBit(unsigned Bit, bool On) {
   assert(Bit < 16 && "SubclassData contains only 16 bits");
   if (On)
     setValueSubclassData(getSubclassDataFromValue() | (1 << Bit));
   else
     setValueSubclassData(getSubclassDataFromValue() & ~(1 << Bit));
 }
 
-void Function::setEntryCount(uint64_t Count,
+void Function::setEntryCount(uint64_t Count, bool Synthetic,
                              const DenseSet<GlobalValue::GUID> *S) {
   MDBuilder MDB(getContext());
-  setMetadata(LLVMContext::MD_prof, MDB.createFunctionEntryCount(Count, S));
+  setMetadata(LLVMContext::MD_prof,
+              MDB.createFunctionEntryCount(Count, Synthetic, S));
 }
 
 Optional<uint64_t> Function::getEntryCount() const {
   MDNode *MD = getMetadata(LLVMContext::MD_prof);
   if (MD && MD->getOperand(0))
     if (MDString *MDS = dyn_cast<MDString>(MD->getOperand(0)))
       if (MDS->getString().equals("function_entry_count")) {
         ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(1));
         uint64_t Count = CI->getValue().getZExtValue();
         // A value of -1 is used for SamplePGO when there were no samples.
         // Treat this the same as unknown.
         if (Count == (uint64_t)-1)
           return None;
         return Count;
       }
   return None;
 }
 
+Optional<uint64_t> Function::getSyntheticEntryCount() const {
+  MDNode *MD = getMetadata(LLVMContext::MD_prof);
+  if (MD && MD->getOperand(0))
+    if (MDString *MDS = dyn_cast<MDString>(MD->getOperand(0)))
+      if (MDS->getString().equals("synthetic_function_entry_count")) {
+        ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(1));
+        uint64_t Count = CI->getValue().getZExtValue();
+        // A value of -1 is used for SamplePGO when there were no samples.
+        // Treat this the same as unknown.
+        if (Count == (uint64_t)-1)
+          return None;
+        return Count;
+      }
+  return None;
+}
+
 DenseSet<GlobalValue::GUID> Function::getImportGUIDs() const {
   DenseSet<GlobalValue::GUID> R;
   if (MDNode *MD = getMetadata(LLVMContext::MD_prof))
     if (MDString *MDS = dyn_cast<MDString>(MD->getOperand(0)))
       if (MDS->getString().equals("function_entry_count"))
         for (unsigned i = 2; i < MD->getNumOperands(); i++)
           R.insert(mdconst::extract<ConstantInt>(MD->getOperand(i))
                        ->getValue()

lib/IR/MDBuilder.cpp

MDNode *MDBuilder::createBranchWeights(ArrayRef<uint32_t> Weights) {
   return MDNode::get(Context, Vals);
 }
 
 MDNode *MDBuilder::createUnpredictable() {
   return MDNode::get(Context, None);
 }
 
 MDNode *MDBuilder::createFunctionEntryCount(
-    uint64_t Count, const DenseSet<GlobalValue::GUID> *Imports) {
+    uint64_t Count, bool Synthetic,
+    const DenseSet<GlobalValue::GUID> *Imports) {
   Type *Int64Ty = Type::getInt64Ty(Context);
   SmallVector<Metadata *, 8> Ops;
+  if (Synthetic)
+    Ops.push_back(createString("synthetic_function_entry_count"));
+  else
     Ops.push_back(createString("function_entry_count"));
   Ops.push_back(createConstant(ConstantInt::get(Int64Ty, Count)));
   if (Imports) {
     SmallVector<GlobalValue::GUID, 2> OrderID(Imports->begin(), Imports->end());
     std::stable_sort(OrderID.begin(), OrderID.end(),
       [] (GlobalValue::GUID A, GlobalValue::GUID B) {
         return A < B;});
     for (auto ID : OrderID)
       Ops.push_back(createConstant(ConstantInt::get(Int64Ty, ID)));

lib/IR/Verifier.cpp

if (Pair.first == LLVMContext::MD_prof) {
 
       // Check first operand.
       Assert(MD->getOperand(0) != nullptr, "first operand should not be null",
              MD);
       Assert(isa<MDString>(MD->getOperand(0)),
              "expected string with name of the !prof annotation", MD);
       MDString *MDS = cast<MDString>(MD->getOperand(0));
       StringRef ProfName = MDS->getString();
-      Assert(ProfName.equals("function_entry_count"),
-             "first operand should be 'function_entry_count'", MD);
+      Assert(ProfName.equals("function_entry_count") ||
+                 ProfName.equals("synthetic_function_entry_count"),
+             "first operand should be 'function_entry_count'"
+             " or 'synthetic_function_entry_count'",
+             MD);
 
       // Check second operand.
       Assert(MD->getOperand(1) != nullptr, "second operand should not be null",
              MD);
       Assert(isa<ConstantAsMetadata>(MD->getOperand(1)),
              "expected integer argument to function_entry_count", MD);
     }
   }

lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/IPO/GlobalSplit.h"
 #include "llvm/Transforms/IPO/InferFunctionAttrs.h"
 #include "llvm/Transforms/IPO/Inliner.h"
 #include "llvm/Transforms/IPO/Internalize.h"
 #include "llvm/Transforms/IPO/LowerTypeTests.h"
 #include "llvm/Transforms/IPO/PartialInlining.h"
 #include "llvm/Transforms/IPO/SCCP.h"
 #include "llvm/Transforms/IPO/StripDeadPrototypes.h"
+#include "llvm/Transforms/IPO/SyntheticCountsPropagation.h"
 #include "llvm/Transforms/IPO/WholeProgramDevirt.h"
 #include "llvm/Transforms/InstCombine/InstCombine.h"
 #include "llvm/Transforms/InstrProfiling.h"
 #include "llvm/Transforms/Instrumentation/BoundsChecking.h"
 #include "llvm/Transforms/PGOInstrumentation.h"
 #include "llvm/Transforms/SampleProfile.h"
 #include "llvm/Transforms/Scalar/ADCE.h"
 #include "llvm/Transforms/Scalar/AlignmentFromAssumptions.h"

 static cl::opt<bool> EnableGVNHoist(
     "enable-npm-gvn-hoist", cl::init(false), cl::Hidden,
     cl::desc("Enable the GVN hoisting pass for the new PM (default = off)"));
 
 static cl::opt<bool> EnableGVNSink(
     "enable-npm-gvn-sink", cl::init(false), cl::Hidden,
     cl::desc("Enable the GVN hoisting pass for the new PM (default = off)"));
 
+static cl::opt<bool> EnableSyntheticCounts(
+    "enable-npm-synthetic-counts", cl::init(false), cl::Hidden, cl::ZeroOrMore,
+    cl::desc("Run synthetic function entry count generation "
+             "pass"));
+
 static Regex DefaultAliasRegex(
     "^(default|thinlto-pre-link|thinlto|lto-pre-link|lto)<(O[0123sz])>$");
 
 static bool isOptimizingForSize(PassBuilder::OptimizationLevel Level) {
   switch (Level) {
   case PassBuilder::O0:
   case PassBuilder::O1:
   case PassBuilder::O2:
PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
   // Add all the requested passes for instrumentation PGO, if requested.
   if (PGOOpt && Phase != ThinLTOPhase::PostLink &&
       (!PGOOpt->ProfileGenFile.empty() || !PGOOpt->ProfileUseFile.empty())) {
     addPGOInstrPasses(MPM, DebugLogging, Level, PGOOpt->RunProfileGen,
                       PGOOpt->ProfileGenFile, PGOOpt->ProfileUseFile);
     MPM.addPass(PGOIndirectCallPromotion(false, false));
   }
 
+  // Synthesize function entry counts for non-PGO compilation.
+  if (EnableSyntheticCounts && !PGOOpt)
+    MPM.addPass(SyntheticCountsPropagation());
+
   // Require the GlobalsAA analysis for the module so we can query it within
   // the CGSCC pipeline.
   MPM.addPass(RequireAnalysisPass<GlobalsAA, Module>());
 
   // Require the ProfileSummaryAnalysis for the module so we can query it within
   // the inliner pass.
   MPM.addPass(RequireAnalysisPass<ProfileSummaryAnalysis, Module>());
 

lib/Passes/PassRegistry.def

 MODULE_PASS("print", PrintModulePass(dbgs()))
 MODULE_PASS("print-lcg", LazyCallGraphPrinterPass(dbgs()))
 MODULE_PASS("print-lcg-dot", LazyCallGraphDOTPrinterPass(dbgs()))
 MODULE_PASS("rewrite-statepoints-for-gc", RewriteStatepointsForGC())
 MODULE_PASS("rewrite-symbols", RewriteSymbolPass())
 MODULE_PASS("rpo-functionattrs", ReversePostOrderFunctionAttrsPass())
 MODULE_PASS("sample-profile", SampleProfileLoaderPass())
 MODULE_PASS("strip-dead-prototypes", StripDeadPrototypesPass())
+MODULE_PASS("synthetic-counts-propagation", SyntheticCountsPropagation())
 MODULE_PASS("wholeprogramdevirt", WholeProgramDevirtPass())
 MODULE_PASS("verify", VerifierPass())
 #undef MODULE_PASS
 
 #ifndef CGSCC_ANALYSIS
 #define CGSCC_ANALYSIS(NAME, CREATE_PASS)
 #endif
 CGSCC_ANALYSIS("no-op-cgscc", NoOpCGSCCAnalysis())

lib/Transforms/IPO/CMakeLists.txt

add_llvm_library(LLVMipo
   LowerTypeTests.cpp
   MergeFunctions.cpp
   PartialInlining.cpp
   PassManagerBuilder.cpp
   PruneEH.cpp
   SampleProfile.cpp
   StripDeadPrototypes.cpp
   StripSymbols.cpp
+  SyntheticCountsPropagation.cpp
   ThinLTOBitcodeWriter.cpp
   WholeProgramDevirt.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms/IPO
 
   DEPENDS
   intrinsics_gen
   )

lib/Transforms/IPO/SampleProfile.cpp

bool SampleProfileLoader::emitAnnotations(Function &F) {
   Changed |= computeBlockWeights(F);
 
   if (Changed) {
     // Add an entry count to the function using the samples gathered at the
     // function entry.
     // Sets the GUIDs that are inlined in the profiled binary. This is used
     // for ThinLink to make correct liveness analysis, and also make the IR
     // match the profiled binary before annotation.
-    F.setEntryCount(Samples->getHeadSamples() + 1, &InlinedGUIDs);
+    F.setEntryCount(Samples->getHeadSamples() + 1, false, &InlinedGUIDs);
 
     // Compute dominance and loop info needed for propagation.
     computeDominanceAndLoopInfo(F);
 
     // Find equivalence classes.
     findEquivalenceClasses(F);
 
     // Propagate weights to all edges.

lib/Transforms/IPO/SyntheticCountsPropagation.cpp

+//=- SyntheticCountsPropagation.cpp - Propagate function counts --*- 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 synthesizes entry counts for
+// functions and attaches !prof metadata to functions with the synthesized
+// counts. The presence of !prof metadata with counter name set to
+// 'synthesized_function_entry_count' indicate that the value of the counter is
+// an estimation of the likely execution count of the function. This transform
+// is applied only in non PGO mode as functions get 'real' profile-based
+// function entry counts in the PGO mode.
+//
+// The transformation works by first assigning some initial values to the entry
+// counts of all functions and then doing a top-down traversal of the
+// callgraph-scc to propagate the counts. For each function the set of callsites
+// and their relative block frequency is gathered. The relative block frequency
+// multiplied by the entry count of the caller and added to the callee's entry
+// count. For non-trivial SCCs, the new counts are computed from the previous
+// counts and updated in one shot.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/IPO/SyntheticCountsPropagation.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/CallGraph.h"
+#include "llvm/Analysis/SyntheticCountsUtils.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+using Scaled64 = ScaledNumber<uint64_t>;
+
+#define DEBUG_TYPE "synthetic-counts-propagation"
+
+/// Initial synthetic count assigned to functions.
+static cl::opt<int>
+    InitialSyntheticCount("initial-synthetic-count", cl::Hidden, cl::init(10),
+                          cl::ZeroOrMore,
+                          cl::desc("Initial value of synthetic entry count."));
+
+/// Initial synthetic count assigned to inline functions.
+static cl::opt<int> InlineSyntheticCount(
+    "inline-synthetic-count", cl::Hidden, cl::init(15), cl::ZeroOrMore,
+    cl::desc("Initial synthetic entry count for inline functions."));
+
+/// Initial synthetic count assigned to cold functions.
+static cl::opt<int> ColdSyntheticCount(
+    "cold-synthetic-count", cl::Hidden, cl::init(5), cl::ZeroOrMore,
+    cl::desc("Initial synthetic entry count for cold functions."));
+
+// Assign initial synthetic entry counts to functions.
+static void
+initializeCounts(Module &M, function_ref<void(Function *, uint64_t)> SetCount) {
+  auto MayHaveIndirectCalls = [](Function &F) {
+    for (auto *U : F.users()) {
+      if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
+        return true;
+    }
+    return false;
+  };
+
+  for (Function &F : M) {
+    uint64_t InitialCount = InitialSyntheticCount;
+    if (F.isDeclaration())
+      continue;
+    if (F.hasFnAttribute(Attribute::AlwaysInline) ||
+        F.hasFnAttribute(Attribute::InlineHint)) {
+      // Use a higher value for inline functions to account for the fact that
+      // these are usually beneficial to inline.
+      InitialCount = InlineSyntheticCount;
+    } else if (F.hasLocalLinkage() && !MayHaveIndirectCalls(F)) {
+      // Local functions without inline hints get counts only through
+      // propagation.
+      InitialCount = 0;
+    } else if (F.hasFnAttribute(Attribute::Cold) ||
+               F.hasFnAttribute(Attribute::NoInline)) {
+      // Use a lower value for noinline and cold functions.
+      InitialCount = ColdSyntheticCount;
+    }
+    SetCount(&F, InitialCount);
+  }
+}
+
+PreservedAnalyses SyntheticCountsPropagation::run(Module &M,
+                                                  ModuleAnalysisManager &MAM) {
+  FunctionAnalysisManager &FAM =
+      MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
+  DenseMap<Function *, uint64_t> Counts;
+  // Set initial entry counts.
+  initializeCounts(M, [&](Function *F, uint64_t Count) { Counts[F] = Count; });
+
+  // Compute the relative block frequency for a callsite. Use scaled numbers
+  // and not integers since the relative block frequency could be less than 1.
+  auto GetCallSiteWeight = [&](CallSite CS) {
+    Function *Caller = CS.getCaller();
+    auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(*Caller);
+    BasicBlock *CSBB = CS.getInstruction()->getParent();
+    Scaled64 EntryFreq(BFI.getEntryFreq(), 0);
+    Scaled64 BBFreq(BFI.getBlockFreq(CSBB).getFrequency(), 0);
+    BBFreq /= EntryFreq;
+    return BBFreq;
+  };
+
+  CallGraph CG(M);
+  // Propgate the entry counts on the callgraph.
+  propagateSyntheticCounts(
+      CG, GetCallSiteWeight, [&](Function *F) { return Counts[F]; },
+      [&](Function *F, uint64_t New) { Counts[F] += New; });
+
+  // Set the counts as metadata.
+  for (auto Entry : Counts)
+    Entry.first->setEntryCount(Entry.second, true);
+
+  return PreservedAnalyses::all();
+}

test/Transforms/SyntheticCountsPropagation/initial.ll

+; RUN: opt -passes=synthetic-counts-propagation -S < %s | FileCheck %s
+
+; CHECK-LABEL: define void @foo()
+; CHECK: !prof ![[COUNT1:[0-9]+]]
+define void @foo() {
+  ret void
+}
+
+; CHECK-LABEL: define void @foo_inline() #0
+; CHECK: !prof ![[COUNT2:[0-9]+]]
+define void @foo_inline() #0 {
+  ret void
+}
+
+; CHECK-LABEL: define void @foo_always_inline() #1
+; CHECK: !prof ![[COUNT2]]
+define void @foo_always_inline() #1 {
+  ret void
+}
+
+; CHECK-LABEL: define void @foo_cold() #2
+; CHECK: !prof ![[COUNT3:[0-9]+]]
+define void @foo_cold() #2 {
+  ret void
+}
+
+; CHECK-LABEL: define void @foo_noinline() #3
+; CHECK: !prof ![[COUNT3]]
+define void @foo_noinline() #3 {
+  ret void
+}
+
+; CHECK-LABEL: define internal void @foo_local()
+; CHECK: !prof ![[COUNT4:[0-9]+]]
+define internal void @foo_local() {
+  ret void
+}
+
+; CHECK-LABEL: define internal void @foo_local_escaped()
+; CHECK: !prof ![[COUNT1]]
+define internal void @foo_local_escaped() {
+  ret void
+}
+
+declare void @ext(void ()*)
+
+define void @bar() {
+  call void @ext(void ()* nonnull @foo_local_escaped)
+  ret void
+}
+
+; CHECK-LABEL: define internal void @foo_local_inline() #0
+; CHECK: !prof ![[COUNT2]]
+define internal void @foo_local_inline() #0 {
+  ret void
+}
+
+; CHECK-LABEL: define internal void @foo_local_cold() #2
+; CHECK: !prof ![[COUNT4]]
+define internal void @foo_local_cold() #2 {
+  ret void
+}
+
+; CHECK-LABEL: define linkonce void @foo_linkonce()
+; CHECK: !prof ![[COUNT1]]
+define linkonce void @foo_linkonce() {
+  ret void
+}
+
+; CHECK: ![[COUNT1]] = !{!"synthetic_function_entry_count", i64 10}
+; CHECK: ![[COUNT2]] = !{!"synthetic_function_entry_count", i64 15}
+; CHECK: ![[COUNT3]] = !{!"synthetic_function_entry_count", i64 5}
+; CHECK: ![[COUNT4]] = !{!"synthetic_function_entry_count", i64 0}
+
+attributes #0 = {inlinehint}
+attributes #1 = {alwaysinline}
+attributes #2 = {cold}
+attributes #3 = {noinline}
+

test/Transforms/SyntheticCountsPropagation/prop.ll

+; RUN: opt -passes=synthetic-counts-propagation -S < %s | FileCheck %s
+
+; CHECK-LABEL: define void @level1a(i32 %n)
+; CHECK: !prof ![[COUNT1:[0-9]+]]
+define void @level1a(i32 %n) {
+entry:
+  %cmp = icmp sgt i32 %n, 10
+  br i1 %cmp, label %exit, label %loop
+loop:
+  %i = phi i32 [%n, %entry], [%i1, %loop]
+  call void @level2a(i32 %n)
+  %i1 = sub i32 %i, 1
+  %cmp2 = icmp eq i32 %i1, 0
+  br i1 %cmp2, label %exit, label %loop, !prof !1
+exit:
+  ret void
+}
+
+; CHECK-LABEL: define void @level2a(i32 %n)
+; CHECK: !prof ![[COUNT2:[0-9]+]]
+define void @level2a(i32 %n) {
+  call void @level2b(i32 %n)
+  ret void
+}
+
+; CHECK-LABEL: define void @level2b(i32 %n)
+; CHECK: !prof ![[COUNT2]]
+define void @level2b(i32 %n) {
+entry:
+  call void @level2a(i32 %n)
+  %cmp = icmp eq i32 %n, 0
+  br i1 %cmp, label %then, label %else, !prof !2
+then:
+  call void @level3a(i32 %n)
+  br label %else
+else:
+  ret void
+}
+
+; CHECK-LABEL: define internal void @level3a(i32 %n)
+; CHECK: !prof ![[COUNT3:[0-9]+]]
+define internal void @level3a(i32 %n) {
+  ret void
+}
+
+!1 = !{!"branch_weights", i32 1, i32 99}
+!2 = !{!"branch_weights", i32 1, i32 1}
+; CHECK: ![[COUNT1]] = !{!"synthetic_function_entry_count", i64 10}
+; CHECK: ![[COUNT2]] = !{!"synthetic_function_entry_count", i64 520}
+; CHECK: ![[COUNT3]] = !{!"synthetic_function_entry_count", i64 260}

test/Transforms/SyntheticCountsPropagation/scc.ll

+; RUN: opt -passes=synthetic-counts-propagation -S < %s | FileCheck %s
+
+; CHECK-LABEL: define void @foo()
+; CHECK: !prof ![[COUNT1:[0-9]+]]
+define void @foo() {
+  call void @bar()
+  ret void
+}
+
+; CHECK-LABEL: define void @bar() #0
+; CHECK: !prof ![[COUNT1]]
+define void @bar() #0 {
+  call void @foo()
+  ret void
+}
+
+attributes #0 = {inlinehint}
+
+; CHECK: ![[COUNT1]] = !{!"synthetic_function_entry_count", i64 25}