[BOLT] Add main fragment to function layout

[FPar]

Summary

Functions that do not contain any code still have to be emitted. This
occurs on AArch64 where functions can consist only of a constant island.
To support fragment semantics in code emission, this commits adds a
guaranteed main fragment to function layout. This fragment might be
empty, but allows us omit checks whether the function is empty in most
places.

[FPar]

Rebase

[FPar]

Rebase

[FPar]

Rebase

[FPar]

Cleanup

[rafauler]

LGTM

bolt/include/bolt/Core/FunctionLayout.h

 
 #ifndef BOLT_CORE_FUNCTION_LAYOUT_H
 #define BOLT_CORE_FUNCTION_LAYOUT_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator.h"
+#include "llvm/ADT/iterator_range.h"
 
 namespace llvm {
 namespace bolt {
 
 class BinaryFunction;
 class BinaryBasicBlock;
 class FunctionLayout;
 
public:
   class FragmentIterator
       : public iterator_facade_base<
             FragmentIterator, std::bidirectional_iterator_tag, FunctionFragment,
             std::ptrdiff_t, FunctionFragment *, FunctionFragment> {
     FragmentNum Num;
     const FunctionLayout *Layout;
 
     FragmentIterator(FragmentNum Num, const FunctionLayout *Layout)
-        : Num(Num), Layout(Layout) {}
+        : Num(Num), Layout(Layout) {
+      assert(Num.get() <= Layout->fragment_size() &&
+             "Initializing iterator out of bounds");
+    }
 
   public:
     bool operator==(const FragmentIterator &Other) const {
       return Num == Other.Num;
     }
 
     FunctionFragment operator*() const {
+      assert(Num.get() < Layout->fragment_size() &&
+             "Dereferencing end() iterator (or past it)");
       return FunctionFragment(Num, *Layout);
     }
 
     FragmentIterator &operator++() {
+      assert(Num.get() < Layout->fragment_size() &&
+             "Incrementing iterator past end()");
       Num = FragmentNum(Num.get() + 1);
       return *this;
     }
 
     FragmentIterator &operator--() {
+      assert(Num.get() > 0 && "Decrementing iterator past begin()");
       Num = FragmentNum(Num.get() - 1);
       return *this;
     }
 
     friend class FunctionLayout;
   };
 
   using const_iterator = FragmentIterator;
   using block_const_iterator = BasicBlockListType::const_iterator;
   using block_const_reverse_iterator =
       BasicBlockListType::const_reverse_iterator;
 
 private:
   BasicBlockListType Blocks;
   /// List of indices dividing block list into fragments. To simplify iteration,
   /// we have `Fragments.back()` equals `Blocks.size()`. Hence,
-  /// `Fragments.size()` equals `this->size() + 1`.
-  FragmentListType Fragments = {0};
+  /// `Fragments.size()` equals `this->size() + 1`. Always contains at least one
+  /// fragment.
+  FragmentListType Fragments = {0, 0};
   BasicBlockListType PreviousBlocks;
   FragmentListType PreviousFragments;
 
 public:
   /// Add an empty fragment.
   FunctionFragment addFragment();
 
   /// Return the fragment identified by Num.
public:
 
   /// True if the layout contains at least two non-empty fragments.
   bool isSplit() const;
 
   /// Get the edit distance of the new layout with respect to the previous
   /// layout after basic block reordering.
   uint64_t getEditDistance() const;
 
-  size_t size() const { return Fragments.size() - 1; }
-  bool empty() const { return Fragments.size() == 1; }
-  const_iterator begin() const { return {FragmentNum(0), this}; }
-  const_iterator end() const { return {FragmentNum(size()), this}; }
-  FunctionFragment front() const { return *begin(); }
-  FunctionFragment back() const { return *std::prev(end()); }
-  FunctionFragment operator[](const FragmentNum Num) const {
-    return getFragment(Num);
+  /// True if the function is split into at most 2 fragments. Mostly used for
+  /// checking whether a function can be processed in places that do not support
+  /// multiple fragments yet.
+  bool isHotColdSplit() const { return fragment_size() <= 2; }
+
+  size_t fragment_size() const {
+    assert(Fragments.size() >= 2 &&
+           "Layout should have at least one fragment.");
+    return Fragments.size() - 1;
+  }
+  bool fragment_empty() const { return Fragments.size() == 1; }
+  const_iterator fragment_begin() const { return {FragmentNum(0), this}; }
+  const_iterator fragment_end() const {
+    return {FragmentNum(fragment_size()), this};
+  }
+  iterator_range<const_iterator> fragments() const {
+    return {fragment_begin(), fragment_end()};
   }
 
   size_t block_size() const { return Blocks.size(); }
   bool block_empty() const { return Blocks.empty(); }
   BinaryBasicBlock *block_front() const { return Blocks.front(); }
   BinaryBasicBlock *block_back() const { return Blocks.back(); }
   block_const_iterator block_begin() const { return Blocks.begin(); }
   block_const_iterator block_end() const { return Blocks.end(); }

bolt/lib/Core/BinaryEmitter.cpp

 // emission of code and data into object/binary file.
 //
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Core/BinaryEmitter.h"
 #include "bolt/Core/BinaryContext.h"
 #include "bolt/Core/BinaryFunction.h"
 #include "bolt/Core/DebugData.h"
+#include "bolt/Core/FunctionLayout.h"
 #include "bolt/Utils/CommandLineOpts.h"
 #include "bolt/Utils/Utils.h"
 #include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h"
 #include "llvm/MC/MCSection.h"
 #include "llvm/MC/MCStreamer.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/LEB128.h"
 #include "llvm/Support/SMLoc.h"
bool BinaryEmitter::emitFunction(BinaryFunction &Function, bool EmitColdPart) {
   return true;
 }
 
 void BinaryEmitter::emitFunctionBody(BinaryFunction &BF, bool EmitColdPart,
                                      bool EmitCodeOnly) {
   if (!EmitCodeOnly && EmitColdPart && BF.hasConstantIsland())
     BF.duplicateConstantIslands();
 
+  const FunctionFragment FF = BF.getLayout().getFragment(
+      EmitColdPart ? FragmentNum::cold() : FragmentNum::hot());
+
   // Track the first emitted instruction with debug info.
   bool FirstInstr = true;
-  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
-    if (EmitColdPart != BB->isCold())
-      continue;
-
+  for (BinaryBasicBlock *const BB : FF) {
     if ((opts::AlignBlocks || opts::PreserveBlocksAlignment) &&
         BB->getAlignment() > 1)
       Streamer.emitCodeAlignment(BB->getAlignment(), &*BC.STI,
                                  BB->getAlignmentMaxBytes());
     Streamer.emitLabel(BB->getLabel());
     if (!EmitCodeOnly) {
       if (MCSymbol *EntrySymbol = BF.getSecondaryEntryPointSymbol(*BB))
         Streamer.emitLabel(EntrySymbol);

bolt/lib/Core/BinaryFunction.cpp

for (const std::pair<const uint32_t, MCInst> &II : Instructions) {
         OS << LI->second->getName() << ":\n";
       }
 
       BC.printInstruction(OS, II.second, Offset, this);
     }
   }
 
   StringRef SplitPointMsg = "";
-  for (const FunctionFragment F : Layout) {
+  for (const FunctionFragment FF : Layout.fragments()) {
     OS << SplitPointMsg;
     SplitPointMsg = "-------   HOT-COLD SPLIT POINT   -------\n\n";
-    for (const BinaryBasicBlock *BB : F) {
+    for (const BinaryBasicBlock *BB : FF) {
       OS << BB->getName() << " (" << BB->size()
          << " instructions, align : " << BB->getAlignment() << ")\n";
 
       if (isEntryPoint(*BB)) {
         if (MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(*BB))
           OS << "  Secondary Entry Point: " << EntrySymbol->getName() << '\n';
         else
           OS << "  Entry Point\n";

 bool BinaryFunction::finalizeCFIState() {
   LLVM_DEBUG(
       dbgs() << "Trying to fix CFI states for each BB after reordering.\n");
   LLVM_DEBUG(dbgs() << "This is the list of CFI states for each BB of " << *this
                     << ": ");
 
   const char *Sep = "";
   (void)Sep;
-  for (const FunctionFragment F : Layout) {
+  for (const FunctionFragment FF : Layout.fragments()) {
     // Hot-cold border: at start of each region (with a different FDE) we need
     // to reset the CFI state.
     int32_t State = 0;
 
-    for (BinaryBasicBlock *BB : F) {
+    for (BinaryBasicBlock *BB : FF) {
       const int32_t CFIStateAtExit = BB->getCFIStateAtExit();
 
       // We need to recover the correct state if it doesn't match expected
       // state at BB entry point.
       if (BB->getCFIState() < State) {
         // In this case, State is currently higher than what this BB expect it
         // to be. To solve this, we need to insert CFI instructions to undo
         // the effect of all CFI from BB's state to current State.

bolt/lib/Core/FunctionLayout.cpp

 }
 FunctionFragment::const_iterator FunctionFragment::end() const {
   return Layout.block_begin() + Layout.Fragments[Num.get() + 1];
 }
 BinaryBasicBlock *FunctionFragment::front() const { return *begin(); }
 
 FunctionFragment FunctionLayout::addFragment() {
   Fragments.emplace_back(Blocks.size());
-  return back();
+  return getFragment(FragmentNum(Blocks.size() - 1));
 }
 
 FunctionFragment FunctionLayout::getFragment(FragmentNum Num) const {
   return FunctionFragment(Num, *this);
 }
 
 FunctionFragment
 FunctionLayout::findFragment(const BinaryBasicBlock *BB) const {
   return getFragment(BB->getFragmentNum());
 }
 
 void FunctionLayout::addBasicBlock(BinaryBasicBlock *BB) {
-  if (empty())
-    addFragment();
-
   BB->setLayoutIndex(Blocks.size());
   Blocks.emplace_back(BB);
   ++Fragments.back();
-
   assert(Fragments.back() == Blocks.size());
 }
 
 void FunctionLayout::insertBasicBlocks(BinaryBasicBlock *InsertAfter,
                                        ArrayRef<BinaryBasicBlock *> NewBlocks) {
-  if (empty())
-    addFragment();
-
   const block_iterator InsertBeforePos =
       InsertAfter ? std::next(findBasicBlockPos(InsertAfter)) : Blocks.begin();
   Blocks.insert(InsertBeforePos, NewBlocks.begin(), NewBlocks.end());
 
   unsigned FragmentUpdateStart =
       InsertAfter ? InsertAfter->getFragmentNum().get() + 1 : 1;
   std::for_each(
       Fragments.begin() + FragmentUpdateStart, Fragments.end(),
       [&](unsigned &FragmentOffset) { FragmentOffset += NewBlocks.size(); });
 }
 
 void FunctionLayout::eraseBasicBlocks(
     const DenseSet<const BinaryBasicBlock *> ToErase) {
   auto IsErased = [&](const BinaryBasicBlock *const BB) {
     return ToErase.contains(BB);
   };
   FragmentListType NewFragments;
   NewFragments.emplace_back(0);
-  for (const FunctionFragment F : *this) {
-    unsigned ErasedBlocks = count_if(F, IsErased);
-    unsigned NewFragment = NewFragments.back() + F.size() - ErasedBlocks;
+  for (const FunctionFragment FF : fragments()) {
+    unsigned ErasedBlocks = count_if(FF, IsErased);
+    unsigned NewFragment = NewFragments.back() + FF.size() - ErasedBlocks;
     NewFragments.emplace_back(NewFragment);
   }
   llvm::erase_if(Blocks, IsErased);
   Fragments = std::move(NewFragments);
 }
 
 void FunctionLayout::updateLayoutIndices() const {
   unsigned BlockIndex = 0;
-  for (const FunctionFragment F : *this) {
-    for (BinaryBasicBlock *const BB : F)
+  for (const FunctionFragment FF : fragments()) {
+    for (BinaryBasicBlock *const BB : FF)
       BB->setLayoutIndex(BlockIndex++);
   }
 }
 
 void FunctionLayout::update(const ArrayRef<BinaryBasicBlock *> NewLayout) {
   PreviousBlocks = std::move(Blocks);
   PreviousFragments = std::move(Fragments);
 
   Blocks.clear();
-  Fragments = {0};
+  Fragments = {0, 0};
 
   if (NewLayout.empty())
     return;
 
   copy(NewLayout, std::back_inserter(Blocks));
 
   // Generate fragments
   for (const auto &BB : enumerate(Blocks)) {
     unsigned FragmentNum = BB.value()->getFragmentNum().get();
 
-    assert(FragmentNum + 1 >= size() &&
+    assert(FragmentNum >= fragment_size() - 1 &&
            "Blocks must be arranged such that fragments are monotonically "
            "increasing.");
 
     // Add empty fragments if necessary
-    for (unsigned I = size(); I <= FragmentNum; ++I) {
+    for (unsigned I = fragment_size(); I <= FragmentNum; ++I) {
       addFragment();
       Fragments[I] = BB.index();
     }
 
     // Set the next fragment to point one past the current BB
     Fragments[FragmentNum + 1] = BB.index() + 1;
   }
 
   if (PreviousBlocks == Blocks && PreviousFragments == Fragments) {
     // If new layout is the same as previous layout, clear previous layout so
     // hasLayoutChanged() returns false.
     PreviousBlocks = {};
     PreviousFragments = {};
   }
 }
 
 void FunctionLayout::clear() {
   Blocks = {};
-  Fragments = {0};
+  Fragments = {0, 0};
   PreviousBlocks = {};
-  PreviousFragments = {0};
+  PreviousFragments = {0, 0};
 }
 
 BinaryBasicBlock *FunctionLayout::getBasicBlockAfter(const BinaryBasicBlock *BB,
                                                      bool IgnoreSplits) const {
   const block_const_iterator BBPos = find(Blocks, BB);
   if (BBPos == Blocks.end())
     return nullptr;
 
   const block_const_iterator BlockAfter = std::next(BBPos);
   if (BlockAfter == Blocks.end())
     return nullptr;
 
   if (!IgnoreSplits)
     if (BlockAfter == getFragment(BB->getFragmentNum()).end())
       return nullptr;
 
   return *BlockAfter;
 }
 
 bool FunctionLayout::isSplit() const {
   unsigned NonEmptyFragCount = llvm::count_if(
-      *this, [](const FunctionFragment &F) { return !F.empty(); });
+      fragments(), [](const FunctionFragment &FF) { return !FF.empty(); });
   return NonEmptyFragCount >= 2;
 }
 
 uint64_t FunctionLayout::getEditDistance() const {
   return ComputeEditDistance<BinaryBasicBlock *>(PreviousBlocks, Blocks);
 }
 
 FunctionLayout::block_const_iterator
 FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) const {
   return find(Blocks, BB);
 }
 
 FunctionLayout::block_iterator
 FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) {
   return find(Blocks, BB);
 }