[ThinLTO] (WIP) Include total static callsite counts in function summaries

[tejohnson]

Summary

This is built on top of the call graph summary patch D17212.

Note that this contains debugging code and is not the final patch, just
an FYI.

Initially for use in adjusting inline costs to simulate the
LastCallToStaticBonus. Since we can't internalize aggressively for
ThinLTO like in normal LTO, this can be used to give the bonus to
callsites which are the only callsite to a function, which may then be
linker GC'ed if it is inlined. (The inline cost part is a TODO)

Since I think it might also be useful to see which functions have no
calls to them, I am using a 2-bit field to represent this in the bitcode
summary, which means the call count currently saturates at 3.

I found when running this for SPEC cpu2006 that most calls have no
static callsite. It looks like some of this is due to intra-module
inlining in the -O2 -c step, and some is due to indirect callsites
especially C++ virtual calls. To disambiguate these cases we can either
include an address taken bit in the summary, or for even better
information to guide eventual recursive elimination of unreferenced
functions, include the edges in a reference graph (expanded from the
summary call graph).

include/llvm/Bitcode/LLVMBitCodes.h

enum FunctionSummarySymtabCodes {
     // PERMODULE_NOCALLS: [valueid, linkage, instcount]
     FS_PERMODULE_NOCALLS = 1,
     // PERMODULE_CALLS: [valueid, linkage, instcount,
     //                   n x (valueid, callsitecount)]
     FS_PERMODULE_CALLS = 2,
     // PERMODULE_CALLS_PROFILE: [valueid, linkage, instcount,
     //                           n x (valueid, callsitecount, profilecount)]
     FS_PERMODULE_CALLS_PROFILE = 3,
-    // COMBINED_NOCALLS: [modid, linkage, instcount]
+    // COMBINED_NOCALLS: [modid, linkage, callcount, instcount]
     FS_COMBINED_NOCALLS  = 4,
-    // COMBINED_CALLS: [modid, linkage, instcount, n x (valueid, callsitecount)]
+    // COMBINED_CALLS: [modid, linkage, callcount, instcount,
+    //                  n x (valueid, callsitecount)]
     FS_COMBINED_CALLS  = 5,
-    // COMBINED_CALLS_PROFILE: [modid, linkage, instcount,
+    // COMBINED_CALLS_PROFILE: [modid, linkage, callcount, instcount,
     //                          n x (valueid, callsitecount, profilecount)]
     FS_COMBINED_CALLS_PROFILE  = 6,
   };
 
   enum MetadataCodes {
     METADATA_STRING        = 1,   // MDSTRING:      [values]
     METADATA_VALUE         = 2,   // VALUE:         [type num, value num]
     METADATA_NODE          = 3,   // NODE:          [n x md num]

include/llvm/IR/FunctionInfo.h

private:
   // is likely to be profitable.
   // Other information will be added as the importing is tuned, such
   // as hotness (when profile available), and other function characteristics.
 
   /// Number of instructions (ignoring debug instructions, e.g.) computed
   /// during the initial compile step when the function index is first built.
   unsigned InstCount;
 
+  /// Static number of call sites found via call graph edges in the combined
+  /// index. Saturates at 3.
+  unsigned CallCount;
+
   /// List of <CalleeGUID, CalleeInfo> call edge pairs from this function.
   std::vector<EdgeTy> CallGraphEdgeList;
 
 public:
   /// Summary constructors.
-  FunctionSummary() : InstCount(0) {}
-  FunctionSummary(unsigned NumInsts) : InstCount(NumInsts) {}
+  FunctionSummary() : InstCount(0), CallCount(0) {}
+  FunctionSummary(unsigned NumInsts) : InstCount(NumInsts), CallCount(0) {}
 
   /// Set the path to the module containing this function, for use in
   /// the combined index.
   void setModulePath(StringRef ModPath) { ModulePath = ModPath; }
 
   /// Get the path to the module containing this function.
   StringRef modulePath() const { return ModulePath; }
 
   /// Record linkage type.
   void setFunctionLinkage(GlobalValue::LinkageTypes Linkage) {
     FunctionLinkage = Linkage;
   }
 
   /// Return linkage type recorded for this function.
   GlobalValue::LinkageTypes getFunctionLinkage() const {
     return FunctionLinkage;
   }
 
   /// Set the instruction count for this function.
   void setInstCount(unsigned NumInsts) { InstCount = NumInsts; }
 
   /// Get the instruction count recorded for this function.
   unsigned instCount() const { return InstCount; }
 
+  /// Set the call count for this function.
+  void setCallCount(unsigned NumCalls) { CallCount = NumCalls; }
+
+  /// Get the call count recorded for this function.
+  unsigned callCount() const { return CallCount; }
+
   /// Record a call graph edge from this function to the function identified
   /// by \p CalleeGUID, with \p CalleeInfo including the cumulative profile
   /// count (across all calls from this function) or 0 if no FDO.
   void addCallGraphEdge(uint64_t CalleeGUID, CalleeInfo Info) {
     CallGraphEdgeList.push_back(std::make_pair(CalleeGUID, Info));
   }
 
   /// Return the list of <CalleeGUID, ProfileCount> pairs.

 private:
   /// Map from function name to list of function information instances
   /// for functions of that name (may be duplicates in the COMDAT case, e.g.).
   FunctionInfoMapTy FunctionMap;
 
   /// Holds strings for combined index, mapping to the corresponding module ID.
   ModulePathStringTableTy ModulePathStringTable;
 
+  std::map<uint64_t, std::string> GUIDToNameMap;
+
 public:
   FunctionInfoIndex() = default;
 
   // Disable the copy constructor and assignment operators, so
   // no unexpected copying/moving occurs.
   FunctionInfoIndex(const FunctionInfoIndex &) = delete;
   void operator=(const FunctionInfoIndex &) = delete;
 
public:
   /// Get the list of function info objects for a given function.
   const const_funcinfo_iterator findFunctionInfoList(StringRef FuncName) const {
     return FunctionMap.find(Function::getGUID(FuncName));
   }
 
   /// Add a function info for a function of the given name.
   void addFunctionInfo(StringRef FuncName, std::unique_ptr<FunctionInfo> Info) {
     FunctionMap[Function::getGUID(FuncName)].push_back(std::move(Info));
+    addName(FuncName);
   }
 
   void addFunctionInfo(uint64_t FuncGUID, std::unique_ptr<FunctionInfo> Info) {
     FunctionMap[FuncGUID].push_back(std::move(Info));
   }
 
+  void addName(StringRef FuncName) {
+    GUIDToNameMap[Function::getGUID(FuncName)] = FuncName.str();
+  }
+
+  std::string getName(uint64_t FuncGUID) const {
+    auto I = GUIDToNameMap.find(FuncGUID);
+    assert(I != GUIDToNameMap.end());
+    return I->second;
+  }
+
   /// Iterator to allow writer to walk through table during emission.
   iterator_range<StringMap<uint64_t>::const_iterator>
   modPathStringEntries() const {
     return llvm::make_range(ModulePathStringTable.begin(),
                             ModulePathStringTable.end());
   }
 
   /// Get the module ID recorded for the given module path.

lib/Bitcode/Reader/BitcodeReader.cpp

case bitc::FS_PERMODULE_CALLS_PROFILE: {
         unsigned CalleeValueId = Record[I];
         unsigned CallsiteCount = Record[++I];
         uint64_t ProfileCount = HasProfile ? Record[++I] : 0;
         BitcodeSummary.addCallGraphEdge(
             CalleeValueId, CalleeInfo(CallsiteCount, ProfileCount));
       }
       break;
     }
-    // FS_COMBINED_NOCALLS: [modid, linkage, instcount]
-    // FS_COMBINED_CALLS: [modid, linkage, instcount,
+    // FS_COMBINED_NOCALLS: [modid, linkage, callcount, instcount]
+    // FS_COMBINED_CALLS: [modid, linkage, callcount, instcount,
     //                     n x (valueid, callsitecount)]
-    // FS_COMBINED_CALLS_PROFILE: [modid, linkage, instcount,
+    // FS_COMBINED_CALLS_PROFILE: [modid, linkage, callcount, instcount,
     //                             n x (valueid, callsitecount, profilecount)]
     case bitc::FS_COMBINED_NOCALLS:
     case bitc::FS_COMBINED_CALLS:
     case bitc::FS_COMBINED_CALLS_PROFILE: {
       uint64_t ModuleId = Record[0];
       uint64_t RawLinkage = Record[1];
-      unsigned InstCount = Record[2];
+      unsigned CallCount = Record[2]; // Saturates at 3.
+      unsigned InstCount = Record[3];
       std::unique_ptr<FunctionSummary> FS =
           llvm::make_unique<FunctionSummary>(InstCount);
       FS->setFunctionLinkage(getDecodedLinkage(RawLinkage));
       FS->setModulePath(ModuleIdMap[ModuleId]);
+      FS->setCallCount(CallCount);
       FunctionSummaryIOHelper &BitcodeSummary = SummaryMap[CurRecordBit];
       BitcodeSummary.setFunctionSummary(std::move(FS));
       bool HasProfile = (BitCode == bitc::FS_COMBINED_CALLS_PROFILE);
       assert(BitCode != bitc::FS_COMBINED_NOCALLS || Record.size() < 4);
       // For now save the call graph edges using the recorded ValueId,
       // on the summary helper object. After reading the VST this will
       // be transferred into the function summary in the index, using the
       // callee GUID instead.
-      static int CallGraphEdgeStartIndex = 3;
+      static int CallGraphEdgeStartIndex = 4;
       for (unsigned I = CallGraphEdgeStartIndex, E = Record.size(); I != E;
            ++I) {
         unsigned CalleeValueId = Record[I];
         unsigned CallsiteCount = Record[++I];
         uint64_t ProfileCount = HasProfile ? Record[++I] : 0;
         BitcodeSummary.addCallGraphEdge(
             CalleeValueId, CalleeInfo(CallsiteCount, ProfileCount));
       }

lib/Bitcode/Writer/BitcodeWriter.cpp

WriteCombinedFunctionSummary(const FunctionInfoIndex &I,
                              std::map<uint64_t, unsigned> &GUIDToValueIdMap) {
   Stream.EnterSubblock(bitc::FUNCTION_SUMMARY_BLOCK_ID, 3);
 
   // Abbrev for FS_COMBINED_NOCALLS.
   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
   Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED_NOCALLS));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // modid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 2)); // callcount (saturates at 3)
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
   unsigned FSNoCallsAbbrev = Stream.EmitAbbrev(Abbv);
 
   // Abbrev for FS_COMBINED_CALLS.
   Abbv = new BitCodeAbbrev();
   Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED_CALLS));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // modid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 2)); // callcount (saturates at 3)
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
   Abbv->Add(
       BitCodeAbbrevOp(BitCodeAbbrevOp::Array)); // valueid/callsitecount pairs
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
   unsigned FSCallsAbbrev = Stream.EmitAbbrev(Abbv);
 
   // Abbrev for FS_COMBINED_CALLS_PROFILE.
   Abbv = new BitCodeAbbrev();
   Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED_CALLS_PROFILE));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // modid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 2)); // callcount (saturates at 3)
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
   Abbv->Add(BitCodeAbbrevOp(
       BitCodeAbbrevOp::Array)); // valueid/callsitecount/profilecount triples
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
   unsigned FSCallsProfileAbbrev = Stream.EmitAbbrev(Abbv);
 
+  std::map<unsigned, unsigned> ValueIdToCallCountMap;
+  for (const auto &FII : I) {
+    for (auto &FI : FII.second) {
+      FunctionSummary *FS = FI->functionSummary();
+      assert(FS);
+      for (auto &EI : FS->edges()) {
+        const auto &VMI = GUIDToValueIdMap.find(EI.first);
+        // If this GUID doesn't have an entry, it doesn't have a function
+        // summary and we don't need to record any calls to it.
+        if (VMI == GUIDToValueIdMap.end())
+          continue;
+        ValueIdToCallCountMap[VMI->second] += EI.second.CallsiteCount;
+      }
+    }
+  }
+
+  unsigned TotalSummaries = 0;
+  unsigned CallCounts[4] = {0};
   SmallVector<uint64_t, 64> NameVals;
   for (const auto &FII : I) {
     for (auto &FI : FII.second) {
       FunctionSummary *FS = FI->functionSummary();
       assert(FS);
 
       NameVals.push_back(I.getModuleId(FS->modulePath()));
       NameVals.push_back(getEncodedLinkage(FS->getFunctionLinkage()));
+
+      const auto &VMI = GUIDToValueIdMap.find(FII.first);
+      assert(VMI != GUIDToValueIdMap.end());
+      const auto &VCI = ValueIdToCallCountMap.find(VMI->second);
+      unsigned CallCount = 0;
+      if (VCI != ValueIdToCallCountMap.end()) {
+        assert(VCI->second > 0 && "Expected at least 1 call in map");
+        // Saturate call count at 3
+        CallCount = VCI->second > 3 ? 3 : VCI->second;
+      }
+      NameVals.push_back(CallCount);
+      TotalSummaries++;
+      CallCounts[CallCount]++;
+      errs() << "CC " << I.getName(FII.first) << " : " << VCI->second << "\n";
+
       NameVals.push_back(FS->instCount());
 
       bool HasProfileData = false;
       for (auto &EI : FS->edges()) {
         HasProfileData |= EI.second.ProfileCount != 0;
         if (HasProfileData)
           break;
       }
for (auto &FI : FII.second) {
                                             : bitc::FS_COMBINED_CALLS)
                           : bitc::FS_COMBINED_NOCALLS;
 
       // Emit the finished record.
       Stream.EmitRecord(Code, NameVals, FSAbbrev);
       NameVals.clear();
     }
   }
+  errs() << "TotalSummaries: " << TotalSummaries << " CallCounts:";
+  for (unsigned i=0; i<4; i++)
+    errs() << " " << i << ": " << CallCounts[i];
+  errs() << "\n";
 
   Stream.ExitBlock();
 }
 
 // Create the "IDENTIFICATION_BLOCK_ID" containing a single string with the
 // current llvm version, and a record for the epoch number.
 static void WriteIdentificationBlock(const Module *M, BitstreamWriter &Stream) {
   Stream.EnterSubblock(bitc::IDENTIFICATION_BLOCK_ID, 5);

lib/IR/FunctionInfo.cpp

for (auto &OtherFuncInfoLists : *Other) {
     // the original per-module index. Reset it to the new module path
     // string reference owned by the combined index.
     Info->functionSummary()->setModulePath(ModPath);
 
     // Add new function info to existing list. There may be duplicates when
     // combining FunctionMap entries, due to COMDAT functions. Any local
     // functions were given unique global IDs.
     addFunctionInfo(FuncGUID, std::move(Info));
+    addName(Other->getName(FuncGUID));
   }
 }