[BOLT] Print additional splitting statistics

[FPar]

Summary

Generate splitting statistics per fragment and print them accordingly.

[FPar]

Rebase

bolt/include/bolt/Core/BinaryContext.h

 //===----------------------------------------------------------------------===//
 
 #ifndef BOLT_CORE_BINARY_CONTEXT_H
 #define BOLT_CORE_BINARY_CONTEXT_H
 
 #include "bolt/Core/BinaryData.h"
 #include "bolt/Core/BinarySection.h"
 #include "bolt/Core/DebugData.h"
+#include "bolt/Core/FunctionLayout.h"
 #include "bolt/Core/JumpTable.h"
 #include "bolt/Core/MCPlusBuilder.h"
 #include "bolt/RuntimeLibs/RuntimeLibrary.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/BinaryFormat/Dwarf.h"
public:
 
   /// Return functions in output layout order
   std::vector<BinaryFunction *> getSortedFunctions();
 
   /// Do the best effort to calculate the size of the function by emitting
   /// its code, and relaxing branch instructions. By default, branch
   /// instructions are updated to match the layout. Pass \p FixBranches set to
   /// false if the branches are known to be up to date with the code layout.
-  ///
-  /// Return the pair where the first size is for the main part, and the second
-  /// size is for the cold one.
-  std::pair<size_t, size_t> calculateEmittedSize(BinaryFunction &BF,
+  DenseMap<FragmentNum, size_t> calculateEmittedSize(BinaryFunction &BF,
                                                      bool FixBranches = true);
 
   /// Calculate the size of the instruction \p Inst optionally using a
   /// user-supplied emitter for lock-free multi-thread work. MCCodeEmitter is
   /// not thread safe and each thread should operate with its own copy of it.
   uint64_t
   computeInstructionSize(const MCInst &Inst,
                          const MCCodeEmitter *Emitter = nullptr) const {
     if (auto Size = MIB->getAnnotationWithDefault<uint32_t>(Inst, "Size"))

bolt/include/bolt/Core/FunctionLayout.h

public:
   }
   constexpr bool operator>(const FragmentNum Other) const {
     return Value > Other.Value;
   }
 
   static constexpr FragmentNum main() { return FragmentNum(0); }
   static constexpr FragmentNum cold() { return FragmentNum(1); }
 };
+} // namespace bolt
+
+template <> struct DenseMapInfo<bolt::FragmentNum> {
+  using InnerType = DenseMapInfo<decltype(bolt::FragmentNum().get())>;
+
+  static inline bolt::FragmentNum getEmptyKey() {
+    return bolt::FragmentNum(InnerType::getEmptyKey());
+  }
+
+  static inline bolt::FragmentNum getTombstoneKey() {
+    return bolt::FragmentNum(InnerType::getTombstoneKey());
+  }
 
+  static unsigned getHashValue(const bolt::FragmentNum &Val) {
+    return InnerType::getHashValue(Val.get());
+  }
+
+  static bool isEqual(const bolt::FragmentNum &LHS,
+                      const bolt::FragmentNum &RHS) {
+    return InnerType::isEqual(LHS.get(), RHS.get());
+  }
+};
+
+namespace bolt {
 /// A freestanding subset of contiguous blocks of a function.
 class FunctionFragment {
   using BasicBlockListType = SmallVector<BinaryBasicBlock *, 0>;
   using FragmentListType = SmallVector<unsigned, 0>;
 
 public:
   using iterator = raw_pointer_iterator<BasicBlockListType::const_iterator,
                                         BinaryBasicBlock>;

bolt/include/bolt/Passes/SplitFunctions.h

 //===- bolt/Passes/SplitFunctions.h - Split function code -------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef BOLT_PASSES_SPLIT_FUNCTIONS_H
 #define BOLT_PASSES_SPLIT_FUNCTIONS_H
 
+#include "bolt/Core/BinaryFunction.h"
 #include "bolt/Core/FunctionLayout.h"
 #include "bolt/Passes/BinaryPasses.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/Support/CommandLine.h"
-#include <atomic>
 
 namespace llvm {
 namespace bolt {
 
 /// Strategy used to partition blocks into fragments.
 enum SplitFunctionsStrategy : char {
   /// Split each function into a hot and cold fragment using profiling
   /// information.
private:
 
   /// Merge trampolines into \p Layout without trampolines. The merge will place
   /// a trampoline immediately before its destination. Used to revert the effect
   /// of trampolines after createEHTrampolines().
   BasicBlockOrderType
   mergeEHTrampolines(BinaryFunction &BF, BasicBlockOrderType &Layout,
                      const TrampolineSetType &Trampolines) const;
 
-  std::atomic<uint64_t> SplitBytesHot{0ull};
-  std::atomic<uint64_t> SplitBytesCold{0ull};
-
 public:
   explicit SplitFunctions(const cl::opt<bool> &PrintPass)
       : BinaryFunctionPass(PrintPass) {}
 
   bool shouldOptimize(const BinaryFunction &BF) const override;
 
   const char *getName() const override { return "split-functions"; }
 
   void runOnFunctions(BinaryContext &BC) override;
 };
 
 } // namespace bolt
 } // namespace llvm
 
 #endif

bolt/lib/Core/BinaryContext.cpp

 //===- bolt/Core/BinaryContext.cpp - Low-level context --------------------===//
 //
 // 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 file implements the BinaryContext class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Core/BinaryContext.h"
 #include "bolt/Core/BinaryEmitter.h"
 #include "bolt/Core/BinaryFunction.h"
+#include "bolt/Core/FunctionLayout.h"
 #include "bolt/Utils/CommandLineOpts.h"
 #include "bolt/Utils/NameResolver.h"
 #include "bolt/Utils/Utils.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h"
 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
 #include "llvm/DebugInfo/DWARF/DWARFUnit.h"
 #include "llvm/MC/MCAsmLayout.h"
BinaryContext::createInjectedBinaryFunction(const std::string &Name,
                                             bool IsSimple) {
   InjectedBinaryFunctions.push_back(new BinaryFunction(Name, *this, IsSimple));
   BinaryFunction *BF = InjectedBinaryFunctions.back();
   setSymbolToFunctionMap(BF->getSymbol(), BF);
   BF->CurrentState = BinaryFunction::State::CFG;
   return BF;
 }
 
-std::pair<size_t, size_t>
+DenseMap<FragmentNum, size_t>
 BinaryContext::calculateEmittedSize(BinaryFunction &BF, bool FixBranches) {
   // Adjust branch instruction to match the current layout.
   if (FixBranches)
     BF.fixBranches();
 
   // Create local MC context to isolate the effect of ephemeral code emission.
   IndependentCodeEmitter MCEInstance = createIndependentMCCodeEmitter();
   MCContext *LocalCtx = MCEInstance.LocalCtx.get();
BinaryContext::calculateEmittedSize(BinaryFunction &BF, bool FixBranches) {
   // MCStreamer::Finish(), which does more than we want
   Streamer->emitBytes(StringRef(""));
 
   MCAssembler &Assembler =
       static_cast<MCObjectStreamer *>(Streamer.get())->getAssembler();
   MCAsmLayout Layout(Assembler);
   Assembler.layout(Layout);
 
-  const uint64_t HotSize =
+  DenseMap<FragmentNum, size_t> Result;
+  Result[FragmentNum::main()] =
       Layout.getSymbolOffset(*EndLabel) - Layout.getSymbolOffset(*StartLabel);
-  const uint64_t ColdSize =
-      std::accumulate(SplitLabels.begin(), SplitLabels.end(), 0ULL,
-                      [&](const uint64_t Accu, const LabelRange &Labels) {
-                        return Accu + Layout.getSymbolOffset(*Labels.second) -
-                               Layout.getSymbolOffset(*Labels.first);
-                      });
+  for (const auto &FF : enumerate(BF.getLayout().getSplitFragments())) {
+    const MCSymbol *const SplitStartLabel = SplitLabels[FF.index()].first;
+    const MCSymbol *const SplitEndLabel = SplitLabels[FF.index()].second;
+    Result[FF.value().getFragmentNum()] =
+        Layout.getSymbolOffset(*SplitEndLabel) -
+        Layout.getSymbolOffset(*SplitStartLabel);
+  }
 
   // Clean-up the effect of the code emission.
   for (const MCSymbol &Symbol : Assembler.symbols()) {
     MCSymbol *MutableSymbol = const_cast<MCSymbol *>(&Symbol);
     MutableSymbol->setUndefined();
     MutableSymbol->setIsRegistered(false);
   }
 
-  return std::make_pair(HotSize, ColdSize);
+  return Result;
 }
 
 bool BinaryContext::validateEncoding(const MCInst &Inst,
                                      ArrayRef<uint8_t> InputEncoding) const {
   SmallString<256> Code;
   SmallVector<MCFixup, 4> Fixups;
   raw_svector_ostream VecOS(Code);
 

bolt/lib/Passes/BinaryPasses.cpp

if (BC.HasRelocations)
     return;
 
   if (!opts::UpdateDebugSections)
     return;
 
   // If the function wouldn't fit, mark it as non-simple. Otherwise, we may emit
   // incorrect debug info.
   ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {
-    uint64_t HotSize, ColdSize;
-    std::tie(HotSize, ColdSize) =
+    DenseMap<FragmentNum, size_t> FragmentSizes =
         BC.calculateEmittedSize(BF, /*FixBranches=*/false);
-    if (HotSize > BF.getMaxSize())
+    if (FragmentSizes.lookup(FragmentNum::main()) > BF.getMaxSize())
       BF.setSimple(false);
   };
 
   ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {
     return !shouldOptimize(BF);
   };
 
   ParallelUtilities::runOnEachFunction(

bolt/lib/Passes/PatchEntries.cpp

 //===- bolt/Passes/PatchEntries.cpp - Pass for patching function entries --===//
 //
 // 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 file implements the PatchEntries class that is used for patching
 // the original function entry points.
 //
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Passes/PatchEntries.h"
+#include "bolt/Core/FunctionLayout.h"
 #include "bolt/Utils/NameResolver.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/CommandLine.h"
 
 namespace opts {
 
 extern llvm::cl::OptionCategory BoltCategory;
 
for (Patch &Patch : PendingPatches) {
       PatchFunction->setFileOffset(Patch.FileOffset);
       PatchFunction->setOriginSection(Patch.Section);
 
       InstructionListType Seq;
       BC.MIB->createLongTailCall(Seq, Patch.Symbol, BC.Ctx.get());
       PatchFunction->addBasicBlock()->addInstructions(Seq);
 
       // Verify the size requirements.
-      uint64_t HotSize, ColdSize;
-      std::tie(HotSize, ColdSize) = BC.calculateEmittedSize(*PatchFunction);
-      assert(!ColdSize && "unexpected cold code");
-      assert(HotSize <= PatchSize && "max patch size exceeded");
+      DenseMap<FragmentNum, size_t> FragmentSizes =
+          BC.calculateEmittedSize(*PatchFunction);
+      assert(FragmentSizes.count(FragmentNum::main()) &&
+             "missing main fragment");
+      assert(FragmentSizes.size() == 1 && "unexpected cold code");
+      assert(FragmentSizes.lookup(FragmentNum::main()) <= PatchSize &&
+             "max patch size exceeded");
     }
 
     Function.setIsPatched(true);
   }
 }
 
 } // end namespace bolt
 } // end namespace llvm

bolt/lib/Passes/SplitFunctions.cpp

 //===----------------------------------------------------------------------===//
 
 #include "bolt/Passes/SplitFunctions.h"
 #include "bolt/Core/BinaryBasicBlock.h"
 #include "bolt/Core/BinaryFunction.h"
 #include "bolt/Core/FunctionLayout.h"
 #include "bolt/Core/ParallelUtilities.h"
 #include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/Sequence.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FormatVariadic.h"
 #include <algorithm>
 #include <iterator>
 #include <memory>
 #include <numeric>
struct SplitAll final : public SplitStrategy {
   }
 
   void fragment(const BlockIt Start, const BlockIt End) override {
     unsigned Fragment = 0;
     for (BinaryBasicBlock *const BB : llvm::make_range(Start, End))
       BB->setFragmentNum(FragmentNum(Fragment++));
   }
 };
+
+std::string
+formatFragmentStats(const DenseMap<FragmentNum, size_t> &FragmentSizes) {
+  if (FragmentSizes.empty())
+    return "<no fragments>";
+
+  const size_t TotalSize = std::accumulate(
+      FragmentSizes.begin(), FragmentSizes.end(), (size_t)0,
+      [](const double Accu, const std::pair<FragmentNum, size_t> &FSize) {
+        return Accu + FSize.second;
+      });
+  const double TotalSizeFP = static_cast<double>(TotalSize);
+
+  SmallVector<std::pair<StringRef, size_t>, 3> Stats;
+
+  const size_t MainSize = FragmentSizes.lookup(FragmentNum::main());
+  const size_t F1Size = FragmentSizes.lookup(FragmentNum(1));
+
+  Stats.emplace_back("hot", MainSize);
+  if (FragmentSizes.size() == 2) {
+    Stats.emplace_back("cold", F1Size);
+  } else if (FragmentSizes.size() > 2) {
+    const size_t NonHotSize = TotalSize - MainSize;
+    Stats.emplace_back("non-hot", NonHotSize);
+  }
+
+  SmallVector<SmallString<32>, 3> FormattedStats;
+  for (const std::pair<StringRef, size_t> &Entry : Stats)
+    FormattedStats.emplace_back(formatv("{0}B {1} ({2:p2})", Entry.second,
+                                        Entry.first,
+                                        Entry.second / TotalSizeFP));
+
+  return llvm::join(FormattedStats, ", ");
+}
 } // namespace
 
 namespace llvm {
 namespace bolt {
 
 bool SplitFunctions::shouldOptimize(const BinaryFunction &BF) const {
   // Apply execution count threshold
   if (BF.getKnownExecutionCount() < opts::ExecutionCountThreshold)
ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {
     return !shouldOptimize(BF);
   };
 
   ParallelUtilities::runOnEachFunction(
       BC, ParallelUtilities::SchedulingPolicy::SP_BB_LINEAR,
       [&](BinaryFunction &BF) { splitFunction(BF, *Strategy); }, SkipFunc,
       "SplitFunctions", ForceSequential);
 
-  if (SplitBytesHot + SplitBytesCold > 0)
-    outs() << "BOLT-INFO: splitting separates " << SplitBytesHot
-           << " hot bytes from " << SplitBytesCold << " cold bytes "
-           << format("(%.2lf%% of split functions is hot).\n",
-                     100.0 * SplitBytesHot / (SplitBytesHot + SplitBytesCold));
+  DenseMap<FragmentNum, size_t> TotalFragmentSizes;
+  for (BinaryFunction *const BF : BC.getAllBinaryFunctions()) {
+    const DenseMap<FragmentNum, size_t> FunctionFragmentSizes =
+        BC.calculateEmittedSize(*BF, /*FixBranches=*/false);
+    for (const std::pair<FragmentNum, size_t> &Pair : FunctionFragmentSizes) {
+      const FragmentNum Frag = Pair.first;
+      const size_t Size = Pair.second;
+      TotalFragmentSizes[Frag] += Size;
+    }
+  }
+
+  outs() << formatv("BOLT-INFO: splitting generated {0} fragments with {1}\n",
+                    TotalFragmentSizes.size(),
+                    formatFragmentStats(TotalFragmentSizes));
 }
 
 void SplitFunctions::splitFunction(BinaryFunction &BF, SplitStrategy &S) {
   if (BF.empty())
     return;
 
   if (!S.canSplit(BF))
     return;
 
   FunctionLayout &Layout = BF.getLayout();
   BinaryFunction::BasicBlockOrderType PreSplitLayout(Layout.block_begin(),
                                                      Layout.block_end());
 
   BinaryContext &BC = BF.getBinaryContext();
-  size_t OriginalHotSize;
-  size_t HotSize;
-  size_t ColdSize;
+  size_t OriginalHotSize = 0;
   if (BC.isX86()) {
-    std::tie(OriginalHotSize, ColdSize) = BC.calculateEmittedSize(BF);
-    LLVM_DEBUG(dbgs() << "Estimated size for function " << BF
-                      << " pre-split is <0x"
-                      << Twine::utohexstr(OriginalHotSize) << ", 0x"
-                      << Twine::utohexstr(ColdSize) << ">\n");
+    const DenseMap<FragmentNum, size_t> OriginalFragmentSizes =
+        BC.calculateEmittedSize(BF);
+    OriginalHotSize = OriginalFragmentSizes.lookup(FragmentNum::main());
+    LLVM_DEBUG(
+        dbgs() << formatv(
+            "BOLT-DEBUG: estimated size for function {0} pre-split is {1}\n",
+            BF, formatFragmentStats(OriginalFragmentSizes)));
   }
 
   BinaryFunction::BasicBlockOrderType NewLayout(Layout.block_begin(),
                                                 Layout.block_end());
   // Never outline the first basic block.
   NewLayout.front()->setCanOutline(false);
   for (BinaryBasicBlock *const BB : NewLayout) {
     if (!BB->canOutline())
void SplitFunctions::splitFunction(BinaryFunction &BF, SplitStrategy &S) {
   // have to be placed in the same fragment. When we split them, create
   // trampoline landing pads that will redirect the execution to real LPs.
   TrampolineSetType Trampolines;
   if (!BC.HasFixedLoadAddress && BF.hasEHRanges() && BF.isSplit())
     Trampolines = createEHTrampolines(BF);
 
   // Check the new size to see if it's worth splitting the function.
   if (BC.isX86() && BF.isSplit()) {
-    std::tie(HotSize, ColdSize) = BC.calculateEmittedSize(BF);
-    LLVM_DEBUG(dbgs() << "Estimated size for function " << BF
-                      << " post-split is <0x" << Twine::utohexstr(HotSize)
-                      << ", 0x" << Twine::utohexstr(ColdSize) << ">\n");
+    const DenseMap<FragmentNum, size_t> FragmentSizes =
+        BC.calculateEmittedSize(BF);
+    const size_t NewHotSize = FragmentSizes.lookup(FragmentNum::main());
+    LLVM_DEBUG(
+        dbgs() << formatv(
+            "BOLT-DEBUG: estimated size for function {0} post-split is {1}\n",
+            BF, formatFragmentStats(FragmentSizes)));
     if (alignTo(OriginalHotSize, opts::SplitAlignThreshold) <=
-        alignTo(HotSize, opts::SplitAlignThreshold) + opts::SplitThreshold) {
-      LLVM_DEBUG(dbgs() << "Reversing splitting of function " << BF << ":\n  0x"
-                        << Twine::utohexstr(HotSize) << ", 0x"
-                        << Twine::utohexstr(ColdSize) << " -> 0x"
-                        << Twine::utohexstr(OriginalHotSize) << '\n');
+        alignTo(NewHotSize, opts::SplitAlignThreshold) + opts::SplitThreshold) {
+      LLVM_DEBUG(dbgs() << formatv("BOLT-DEBUG: reversing splitting of "
+                                   "function {0}:\n  {1} -> {2:x+}\n",
+                                   BF, formatFragmentStats(FragmentSizes),
+                                   OriginalHotSize));
 
       // Reverse the action of createEHTrampolines(). The trampolines will be
       // placed immediately before the matching destination resulting in no
       // extra code.
       if (PreSplitLayout.size() != BF.size())
         PreSplitLayout = mergeEHTrampolines(BF, PreSplitLayout, Trampolines);
 
       for (BinaryBasicBlock &BB : BF)
         BB.setFragmentNum(FragmentNum::main());
       BF.getLayout().update(PreSplitLayout);
-    } else {
-      SplitBytesHot += HotSize;
-      SplitBytesCold += ColdSize;
     }
   }
 }
 
 SplitFunctions::TrampolineSetType
 SplitFunctions::createEHTrampolines(BinaryFunction &BF) const {
   const auto &MIB = BF.getBinaryContext().MIB;