[BOLT] Change call count output for ICF

[maksfb]

Summary

ICF optimization runs multiple passes and the order in which functions
are folded could be dependent on the order they are being processed.
This order is indeterministic as functions are intermediately stored in
std::unordered_map<>. Note that this order is mostly stable, but is not
guaranteed to be and can change e.g. after switching to a different C++
library implementation.

Because the processing (and folding) order is indeterministic, the
previous way of calculating merged function call count could produce
different results.

Change the way we calculate the ICF call count to make it independent of
the function folding/processing order.

Mostly NFC as the output binary should remain the same, the change
affects only the console output.

[yota9]

bolt/lib/Core/BinaryContext.cpp

1349

Just curious may we just call ChildBF.setFolded(&ParentBF) here? AFAIU it is done only for non-relocation mode since there were no need to mark folded function in rel mode since we're just removing them from the map. If we would still mark function as folded here we may just check isFolded() state in ICF pass.

[maksfb]

bolt/lib/Core/BinaryContext.cpp

1349

In relocation mode, ChildBF will be deleted at this point. Are you suggesting to mark ParentBF as folded?

[yota9]

bolt/lib/Core/BinaryContext.cpp

1349

Oh you are right, for some reason I thought it is adress->pointer map.
Maybe we can use another naming then? Maybe like hasFoldedInto or isParentBF IDK. Merged sounds like the function is merged, not something into it)

[maksfb]

Rename isMerged() -> hasFunctionsFoldedInto()

[yota9]

LGTM Thank you!

[maksfb]

Rebase

bolt/include/bolt/Core/BinaryFunction.h

private:
 
   /// True if there are no control-flow edges with successors in other functions
   /// (i.e. if tail calls have edges to function-local basic blocks).
   /// Set to false by SCTC. Dynostats can't be reliably computed for
   /// functions with non-canonical CFG.
   /// This attribute is only valid when hasCFG() == true.
   bool HasCanonicalCFG{true};
 
+  /// True if another function body was merged into this one.
+  bool HasFunctionsFoldedInto{false};
+
   /// Name for the section this function code should reside in.
   std::string CodeSectionName;
 
   /// Name for the corresponding cold code section.
   std::string ColdCodeSectionName;
 
   /// Parent function fragment for split function fragments.
   SmallPtrSet<BinaryFunction *, 1> ParentFragments;
public:
   /// but not yet populated into the function.
   bool hasProfileAvailable() const { return HasProfileAvailable; }
 
   bool hasMemoryProfile() const { return HasMemoryProfile; }
 
   /// Return true if the body of the function was merged into another function.
   bool isFolded() const { return FoldedIntoFunction != nullptr; }
 
+  /// Return true if other functions were folded into this one.
+  bool hasFunctionsFoldedInto() const { return HasFunctionsFoldedInto; }
+
   /// If this function was folded, return the function it was folded into.
   BinaryFunction *getFoldedIntoFunction() const { return FoldedIntoFunction; }
 
   /// Return true if the function uses jump tables.
   bool hasJumpTables() const { return !JumpTables.empty(); }
 
   /// Return true if the function has SDT marker
   bool hasSDTMarker() const { return HasSDTMarker; }

   void setHasIndirectTargetToSplitFragment(bool V) {
     HasIndirectTargetToSplitFragment = V;
   }
 
   void setHasCanonicalCFG(bool V) { HasCanonicalCFG = V; }
 
   void setFolded(BinaryFunction *BF) { FoldedIntoFunction = BF; }
 
+  /// Indicate that another function body was merged with this function.
+  void setHasFunctionsFoldedInto() { HasFunctionsFoldedInto = true; }
+
   BinaryFunction &setPersonalityFunction(uint64_t Addr) {
     assert(!PersonalityFunction && "can't set personality function twice");
     PersonalityFunction = BC.getOrCreateGlobalSymbol(Addr, "FUNCat");
     return *this;
   }
 
   BinaryFunction &setPersonalityEncoding(uint8_t Encoding) {
     PersonalityEncoding = Encoding;

bolt/lib/Core/BinaryContext.cpp

if (HasRelocations) {
     std::string NewName = "__ICF_" + ChildName.str();
 
     WriteCtxLock.lock();
     ChildBF.getSymbols().push_back(Ctx->getOrCreateSymbol(NewName));
     WriteCtxLock.unlock();
 
     ChildBF.setFolded(&ParentBF);
   }
+
+  ParentBF.setHasFunctionsFoldedInto();
 }
 
 void BinaryContext::fixBinaryDataHoles() {
   assert(validateObjectNesting() && "object nesting inconsitency detected");
 
   for (BinarySection &Section : allocatableSections()) {
     std::vector<std::pair<uint64_t, uint64_t>> Holes;
 

bolt/lib/Passes/IdenticalCodeFolding.cpp

 namespace llvm {
 namespace bolt {
 
 void IdenticalCodeFolding::runOnFunctions(BinaryContext &BC) {
   const size_t OriginalFunctionCount = BC.getBinaryFunctions().size();
   uint64_t NumFunctionsFolded = 0;
   std::atomic<uint64_t> NumJTFunctionsFolded{0};
   std::atomic<uint64_t> BytesSavedEstimate{0};
-  std::atomic<uint64_t> CallsSavedEstimate{0};
+  std::atomic<uint64_t> NumCalled{0};
   std::atomic<uint64_t> NumFoldedLastIteration{0};
   CongruentBucketsMap CongruentBuckets;
 
   // Hash all the functions
   auto hashFunctions = [&]() {
     NamedRegionTimer HashFunctionsTimer("hashing", "hashing", "ICF breakdown",
                                         "ICF breakdown", opts::TimeICF);
     ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {
auto processSingleBucket = [&](std::set<BinaryFunction *> &Candidates) {
         // Fold functions. Keep the order consistent across invocations with
         // different options.
         llvm::stable_sort(
             Twins, [](const BinaryFunction *A, const BinaryFunction *B) {
               return A->getFunctionNumber() < B->getFunctionNumber();
             });
 
         BinaryFunction *ParentBF = Twins[0];
+        if (!ParentBF->hasFunctionsFoldedInto())
+          NumCalled += ParentBF->getKnownExecutionCount();
         for (unsigned I = 1; I < Twins.size(); ++I) {
           BinaryFunction *ChildBF = Twins[I];
           LLVM_DEBUG(dbgs() << "BOLT-DEBUG: folding " << *ChildBF << " into "
                             << *ParentBF << '\n');
 
           // Remove child function from the list of candidates.
           auto FI = Candidates.find(ChildBF);
           assert(FI != Candidates.end() &&
                  "function expected to be in the set");
           Candidates.erase(FI);
 
           // Fold the function and remove from the list of processed functions.
           BytesSavedEstimate += ChildBF->getSize();
-          CallsSavedEstimate += std::min(ChildBF->getKnownExecutionCount(),
-                                         ParentBF->getKnownExecutionCount());
+          if (!ChildBF->hasFunctionsFoldedInto())
+            NumCalled += ChildBF->getKnownExecutionCount();
           BC.foldFunction(*ChildBF, *ParentBF);
 
           ++NumFoldedLastIteration;
 
           if (ParentBF->hasJumpTables())
             ++NumJTFunctionsFolded;
         }
       }
void IdenticalCodeFolding::runOnFunctions(BinaryContext &BC) {
 
   if (NumFunctionsFolded)
     outs() << "BOLT-INFO: ICF folded " << NumFunctionsFolded << " out of "
            << OriginalFunctionCount << " functions in " << Iteration
            << " passes. " << NumJTFunctionsFolded
            << " functions had jump tables.\n"
            << "BOLT-INFO: Removing all identical functions will save "
            << format("%.2lf", (double)BytesSavedEstimate / 1024)
-           << " KB of code space. Folded functions were called "
-           << CallsSavedEstimate << " times based on profile.\n";
+           << " KB of code space. Folded functions were called " << NumCalled
+           << " times based on profile.\n";
 }
 
 } // namespace bolt
 } // namespace llvm