[BOLT] Add function layout class

[FPar]

Summary

This patch adds a dedicated class to keep track of each function's
layout. It also lays the groundwork for splitting functions into
multiple fragments (as opposed to a strict hot/cold split).

[yota9]

bolt/include/bolt/Core/BinaryBasicBlock.h

683

Hello, I didn't investigate this patch carefully for now, but why FragmentNum needs to be unsigned? It seems it is used like previously used isCold flag.

[FPar]

bolt/include/bolt/Core/BinaryBasicBlock.h

683

It is unsigned, because it will be used to reference the fragment in which the basic block resides. You are correct that as of this patch there is only a hot and cold fragment and FragmentNum only assumes values 0 or 1. This will change with subsequent patches, in which support for multiple fragment splitting will be introduced.

For this patch, I'll change the definition of getFragmentNum() to depend on IsCold, and retain the original definition for isCold()/setIsCold().

[FPar]

Split diff to reduce noise from replacing references to function layout to
block list.

[FPar]

Rebase on previous commit

[tschuett]

bolt/include/bolt/Core/FunctionLayout.h

43

If you use an enum class, then you can get rid of the prefixes.

[FPar]

bolt/include/bolt/Core/FunctionLayout.h

43

This enum is to be used temporarily to pass into APIs that take a fragment number as parameter for parts of BOLT that are only hot/cold aware (so we can perform a more incremental transition from relying on .blocks() to being fully multi-fragment aware). The code using those values will be nicer if they automatically convert to unsigned. Thanks for looking over this!

[FPar]

Move FunctionFragment out of FunctionLayout class

[tschuett]

Just as a comment. Maybe down the line, you could replace the unsigned with a FragmentId, a wrapper around an unsigned, to avoid confusion.

I have a feeling that you want to deprecate FunctionLayout::blocks(). There is probably a LLVM_DEPRECATED macro.

[FPar]

Wrap FragmentNum in new type

[FPar]

In D129518#3649320, @tschuett wrote:

Just as a comment. Maybe down the line, you could replace the unsigned with a FragmentId, a wrapper around an unsigned, to avoid confusion.

I have a feeling that you want to deprecate FunctionLayout::blocks(). There is probably a LLVM_DEPRECATED macro.

Your intution is correct, we want to get rid of FunctionLayout::blocks(). We discussed marking it as deprecated, but we figured it'll mostly create warning noise for now, because it is used too pervasively. So we defer that for now.

I did add a type for FragmentNum. I want to avoid the term "Id" here, because it is not used as an identifier across functions and can change arbitrarily in case if fragments are inserted in the middle of a function. Thanks for the suggestion!

[maksfb]

bolt/include/bolt/Core/BinaryFunction.h

1376–1377

What do you think of making isSplit() a property of FunctionLayout? We can keep this method as it also uses isSimple() for the sake of NFC, but perhaps this check is unnecessary.

bolt/include/bolt/Core/FunctionLayout.h

80

177

bolt/lib/Core/BinaryEmitter.cpp

401

We can take advantage of the new layout class and iterate over fragments here.

bolt/lib/Core/BinaryFunction.cpp

3232–3233

3566

[FPar]

Add isSplit() method to FunctionLayout + fix nits

bolt/include/bolt/Core/BinaryFunction.h

1376–1377

I agree.

bolt/lib/Core/BinaryEmitter.cpp

401

I already have considered something like this:

const FunctionFragment F = BF.getLayout().getFragment(
      EmitColdPart ? FragmentNum::cold() : FragmentNum::hot());
  for (BinaryBasicBlock *BB : F) {

This change causes the AArch64 tests to fail, because this function is called (with EmitColdPart==false) even when the layout is empty. There are a few options to resolve this: separate the function into two functions, such that one deals with the constant islands and the other one emits the fragments. Then either one calls the other, or you update all callsites. The other option is to wrap the for (BinaryBasicBlock *BB... in a conditional. The last option is two return a default/null fragment from FunctionLayout::getFragment(), but I'd like to avoid adding those semantics to FunctionFragment.

The first solution is probably the correct one, but adds extra noise to this diff. The second solution creates a lot of indenting. Either way, this will eventually be rewritten to support more than two fragments. Unless you think we should change it regardless, I'd suggest we keep iterating over the blocks, for now.

[rafauler]

bolt/lib/Core/FunctionLayout.cpp

105

monotonically? unless the blocks are boring

[maksfb]

bolt/include/bolt/Core/FunctionLayout.h

12–15

62

Will the reference work?

[maksfb]

LGTM

bolt/include/bolt/Core/BinaryFunction.h

2332

Same as block_front() (same for the next three occurrences)?

bolt/include/bolt/Core/FunctionLayout.h

82

149

[FPar]

Address feedback

bolt/include/bolt/Core/BinaryBasicBlock.h

 // CFI instructions are part of the instruction list with the initial CFI state
 // defined at the beginning of the block.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef BOLT_CORE_BINARY_BASIC_BLOCK_H
 #define BOLT_CORE_BINARY_BASIC_BLOCK_H
 
+#include "bolt/Core/FunctionLayout.h"
 #include "bolt/Core/MCPlus.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/MC/MCSymbol.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/raw_ostream.h"
 #include <limits>
public:
   /// Return true if the basic block is an entry point into the function
   /// (either primary or secondary).
   bool isEntryPoint() const;
 
   bool isValid() const { return IsValid; }
 
   void markValid(const bool Valid) { IsValid = Valid; }
 
+  FragmentNum getFragmentNum() const {
+    return IsCold ? FragmentNum::cold() : FragmentNum::hot();
+  }
+
   bool isCold() const { return IsCold; }
 
   void setIsCold(const bool Flag) { IsCold = Flag; }
 
   /// Return true if the block can be outlined. At the moment we disallow
   /// outlining of blocks that can potentially throw exceptions or are
   /// the beginning of a landing pad. The entry basic block also can
   /// never be outlined.
   bool canOutline() const { return CanOutline; }
 
   void setCanOutline(const bool Flag) { CanOutline = Flag; }
 
   /// Erase pseudo instruction at a given iterator.

bolt/include/bolt/Core/BinaryFunction.h

 #ifndef BOLT_CORE_BINARY_FUNCTION_H
 #define BOLT_CORE_BINARY_FUNCTION_H
 
 #include "bolt/Core/BinaryBasicBlock.h"
 #include "bolt/Core/BinaryContext.h"
 #include "bolt/Core/BinaryLoop.h"
 #include "bolt/Core/BinarySection.h"
 #include "bolt/Core/DebugData.h"
+#include "bolt/Core/FunctionLayout.h"
 #include "bolt/Core/JumpTable.h"
 #include "bolt/Core/MCPlus.h"
 #include "bolt/Utils/NameResolver.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/MC/MCContext.h"
 #include "llvm/MC/MCDwarf.h"
private:
   std::unique_ptr<IslandInfo> Islands;
 
   // Blocks are kept sorted in the layout order. If we need to change the
   // layout (if BasicBlocksLayout stores a different order than BasicBlocks),
   // the terminating instructions need to be modified.
   using BasicBlockListType = SmallVector<BinaryBasicBlock *, 0>;
   BasicBlockListType BasicBlocks;
   BasicBlockListType DeletedBasicBlocks;
-  BasicBlockOrderType BasicBlocksLayout;
-  /// Previous layout replaced by modifyLayout
-  BasicBlockOrderType BasicBlocksPreviousLayout;
-  bool ModifiedLayout{false};
+
+  FunctionLayout Layout;
 
   /// BasicBlockOffsets are used during CFG construction to map from code
   /// offsets to BinaryBasicBlocks.  Any modifications made to the CFG
   /// after initial construction are not reflected in this data structure.
   using BasicBlockOffset = std::pair<uint64_t, BinaryBasicBlock *>;
   struct CompareBasicBlockOffsets {
     bool operator()(const BasicBlockOffset &A,
                     const BasicBlockOffset &B) const {
public:
 
   using iterator = pointee_iterator<BasicBlockListType::iterator>;
   using const_iterator = pointee_iterator<BasicBlockListType::const_iterator>;
   using reverse_iterator =
       pointee_iterator<BasicBlockListType::reverse_iterator>;
   using const_reverse_iterator =
       pointee_iterator<BasicBlockListType::const_reverse_iterator>;
 
-  typedef BasicBlockOrderType::iterator order_iterator;
-  typedef BasicBlockOrderType::const_iterator const_order_iterator;
-  typedef BasicBlockOrderType::reverse_iterator reverse_order_iterator;
-  typedef BasicBlockOrderType::const_reverse_iterator
-      const_reverse_order_iterator;
-
   // CFG iterators.
   iterator                 begin()       { return BasicBlocks.begin(); }
   const_iterator           begin() const { return BasicBlocks.begin(); }
   iterator                 end  ()       { return BasicBlocks.end();   }
   const_iterator           end  () const { return BasicBlocks.end();   }
 
   reverse_iterator        rbegin()       { return BasicBlocks.rbegin(); }
   const_reverse_iterator  rbegin() const { return BasicBlocks.rbegin(); }
public:
   inline iterator_range<const_iterator> blocks() const {
     return iterator_range<const_iterator>(begin(), end());
   }
 
   // Iterators by pointer.
   BasicBlockListType::iterator pbegin()  { return BasicBlocks.begin(); }
   BasicBlockListType::iterator pend()    { return BasicBlocks.end(); }
 
-  order_iterator       layout_begin()    { return BasicBlocksLayout.begin(); }
-  const_order_iterator layout_begin()    const
-                                         { return BasicBlocksLayout.begin(); }
-  order_iterator       layout_end()      { return BasicBlocksLayout.end(); }
-  const_order_iterator layout_end()      const
-                                         { return BasicBlocksLayout.end(); }
-  reverse_order_iterator       layout_rbegin()
-                                         { return BasicBlocksLayout.rbegin(); }
-  const_reverse_order_iterator layout_rbegin() const
-                                         { return BasicBlocksLayout.rbegin(); }
-  reverse_order_iterator       layout_rend()
-                                         { return BasicBlocksLayout.rend(); }
-  const_reverse_order_iterator layout_rend()   const
-                                         { return BasicBlocksLayout.rend(); }
-  size_t   layout_size()  const { return BasicBlocksLayout.size(); }
-  bool     layout_empty() const { return BasicBlocksLayout.empty(); }
-  const BinaryBasicBlock *layout_front() const
-                                         { return BasicBlocksLayout.front(); }
-        BinaryBasicBlock *layout_front() { return BasicBlocksLayout.front(); }
-  const BinaryBasicBlock *layout_back()  const
-                                         { return BasicBlocksLayout.back(); }
-        BinaryBasicBlock *layout_back()  { return BasicBlocksLayout.back(); }
-
-  inline iterator_range<order_iterator> layout() {
-    return iterator_range<order_iterator>(BasicBlocksLayout.begin(),
-                                          BasicBlocksLayout.end());
-  }
-
-  inline iterator_range<const_order_iterator> layout() const {
-    return iterator_range<const_order_iterator>(BasicBlocksLayout.begin(),
-                                                BasicBlocksLayout.end());
-  }
-
-  inline iterator_range<reverse_order_iterator> rlayout() {
-    return iterator_range<reverse_order_iterator>(BasicBlocksLayout.rbegin(),
-                                                  BasicBlocksLayout.rend());
-  }
-
-  inline iterator_range<const_reverse_order_iterator> rlayout() const {
-    return iterator_range<const_reverse_order_iterator>(
-        BasicBlocksLayout.rbegin(), BasicBlocksLayout.rend());
-  }
-
   cfi_iterator        cie_begin()       { return CIEFrameInstructions.begin(); }
   const_cfi_iterator  cie_begin() const { return CIEFrameInstructions.begin(); }
   cfi_iterator        cie_end()         { return CIEFrameInstructions.end(); }
   const_cfi_iterator  cie_end()   const { return CIEFrameInstructions.end(); }
   bool                cie_empty() const { return CIEFrameInstructions.empty(); }
 
   inline iterator_range<cfi_iterator> cie() {
     return iterator_range<cfi_iterator>(cie_begin(), cie_end());
public:
   /// Returns the raw binary encoding of this function.
   ErrorOr<ArrayRef<uint8_t>> getData() const;
 
   BinaryFunction &updateState(BinaryFunction::State State) {
     CurrentState = State;
     return *this;
   }
 
-  /// Update layout of basic blocks used for output.
-  void updateBasicBlockLayout(BasicBlockOrderType &NewLayout) {
-    assert(NewLayout.size() == BasicBlocks.size() && "Layout size mismatch.");
-
-    BasicBlocksPreviousLayout = BasicBlocksLayout;
-    if (NewLayout != BasicBlocksLayout) {
-      ModifiedLayout = true;
-      BasicBlocksLayout.clear();
-      BasicBlocksLayout.swap(NewLayout);
-    }
-  }
+  FunctionLayout &getLayout() { return Layout; }
+
+  const FunctionLayout &getLayout() const { return Layout; }
 
   /// Recompute landing pad information for the function and all its blocks.
   void recomputeLandingPads();
 
-  /// Return current basic block layout.
-  const BasicBlockOrderType &getLayout() const { return BasicBlocksLayout; }
-
   /// Return a list of basic blocks sorted using DFS and update layout indices
   /// using the same order. Does not modify the current layout.
-  BasicBlockOrderType dfs() const;
+  BasicBlockListType dfs() const;
 
   /// Find the loops in the CFG of the function and store information about
   /// them.
   void calculateLoopInfo();
 
   /// Calculate missed macro-fusion opportunities and update BinaryContext
   /// stats.
   void calculateMacroOpFusionStats();
BinaryBasicBlock *getBasicBlockForLabel(const MCSymbol *Label) {
     return I == LabelToBB.end() ? nullptr : I->second;
   }
 
   const BinaryBasicBlock *getBasicBlockForLabel(const MCSymbol *Label) const {
     auto I = LabelToBB.find(Label);
     return I == LabelToBB.end() ? nullptr : I->second;
   }
 
-  /// Returns the basic block after the given basic block in the layout or
-  /// nullptr the last basic block is given.
-  const BinaryBasicBlock *getBasicBlockAfter(const BinaryBasicBlock *BB,
-                                             bool IgnoreSplits = true) const {
-    return const_cast<BinaryFunction *>(this)->getBasicBlockAfter(BB,
-                                                                  IgnoreSplits);
-  }
-
-  BinaryBasicBlock *getBasicBlockAfter(const BinaryBasicBlock *BB,
-                                       bool IgnoreSplits = true) {
-    for (auto I = layout_begin(), E = layout_end(); I != E; ++I) {
-      auto Next = std::next(I);
-      if (*I == BB && Next != E) {
-        return (IgnoreSplits || (*I)->isCold() == (*Next)->isCold()) ? *Next
-                                                                     : nullptr;
-      }
-    }
-    return nullptr;
-  }
-
   /// Retrieve the landing pad BB associated with invoke instruction \p Invoke
   /// that is in \p BB. Return nullptr if none exists
   BinaryBasicBlock *getLandingPadBBFor(const BinaryBasicBlock &BB,
                                        const MCInst &InvokeInst) const {
     assert(BC.MIB->isInvoke(InvokeInst) && "must be invoke instruction");
     const Optional<MCPlus::MCLandingPad> LP = BC.MIB->getEHInfo(InvokeInst);
     if (LP && LP->first) {
       BinaryBasicBlock *LBB = BB.getLandingPad(LP->first);
public:
 
   /// Return true if the original function code has all necessary relocations
   /// to track addresses of functions emitted to new locations.
   bool hasExternalRefRelocations() const { return HasExternalRefRelocations; }
 
   /// Return true if the function has instruction(s) with unknown control flow.
   bool hasUnknownControlFlow() const { return HasUnknownControlFlow; }
 
   /// Return true if the function body is non-contiguous.
-  bool isSplit() const {
-    return isSimple() && layout_size() &&
-           layout_front()->isCold() != layout_back()->isCold();
-  }
+  bool isSplit() const { return isSimple() && getLayout().isSplit(); }
 
   bool shouldPreserveNops() const { return PreserveNops; }
 
   /// Return true if the function has exception handling tables.
   bool hasEHRanges() const { return HasEHRanges; }
 
   /// Return true if the function uses DW_CFA_GNU_args_size CFIs.
   bool usesGnuArgsSize() const { return UsesGnuArgsSize; }
public:
   /// of basic blocks of this function.
   BinaryBasicBlock *addBasicBlock(MCSymbol *Label = nullptr) {
     assert(CurrentState == State::CFG && "Can only add blocks in CFG state");
 
     BasicBlocks.emplace_back(createBasicBlock(Label).release());
     BinaryBasicBlock *BB = BasicBlocks.back();
 
     BB->setIndex(BasicBlocks.size() - 1);
-    BB->setLayoutIndex(layout_size());
-    BasicBlocksLayout.emplace_back(BB);
+    Layout.addBasicBlock(BB);
 
     return BB;
   }
 
   /// Add basic block \BB as an entry point to the function. Return global
   /// symbol associated with the entry.
   MCSymbol *addEntryPoint(const BinaryBasicBlock &BB);
 
iterator insertBasicBlocks(
       const bool UpdateLayout = true, const bool UpdateCFIState = true,
       const bool RecomputeLandingPads = true);
 
   /// Update the basic block layout for this function.  The BBs from
   /// [Start->Index, Start->Index + NumNewBlocks) are inserted into the
   /// layout after the BB indicated by Start.
   void updateLayout(BinaryBasicBlock *Start, const unsigned NumNewBlocks);
 
-  /// Make sure basic blocks' indices match the current layout.
-  void updateLayoutIndices() const {
-    unsigned Index = 0;
-    for (BinaryBasicBlock *BB : layout())
-      BB->setLayoutIndex(Index++);
-  }
-
   /// Recompute the CFI state for NumNewBlocks following Start after inserting
   /// new blocks into the CFG.  This must be called after updateLayout.
   void updateCFIState(BinaryBasicBlock *Start, const unsigned NumNewBlocks);
 
   /// Return true if we detected ambiguous jump tables in this function, which
   /// happen when one JT is used in more than one indirect jumps. This precludes
   /// us from splitting edges for this JT unless we duplicate the JT (see
   /// disambiguateJumpTables).

 
   // Convert COUNT_NO_PROFILE to 0
   void removeTagsFromProfile();
 
   /// Computes a function hotness score: the sum of the products of BB frequency
   /// and size.
   uint64_t getFunctionScore() const;
 
-  /// Return true if the layout has been changed by basic block reordering,
-  /// false otherwise.
-  bool hasLayoutChanged() const;
-
-  /// Get the edit distance of the new layout with respect to the previous
-  /// layout after basic block reordering.
-  uint64_t getEditDistance() const;
-
   /// Get the number of instructions within this function.
   uint64_t getInstructionCount() const;
 
   const CFIInstrMapType &getFDEProgram() const { return FrameInstructions; }
 
   void moveRememberRestorePair(BinaryBasicBlock *BB);
 
   bool replayCFIInstrs(int32_t FromState, int32_t ToState,

 
 } // namespace bolt
 
 // GraphTraits specializations for function basic block graphs (CFGs)
 template <>
 struct GraphTraits<bolt::BinaryFunction *>
     : public GraphTraits<bolt::BinaryBasicBlock *> {
   static NodeRef getEntryNode(bolt::BinaryFunction *F) {
-    return *F->layout_begin();
+    return F->getLayout().block_front();
   }
 
   using nodes_iterator = pointer_iterator<bolt::BinaryFunction::iterator>;
 
   static nodes_iterator nodes_begin(bolt::BinaryFunction *F) {
     llvm_unreachable("Not implemented");
     return nodes_iterator(F->begin());
   }
   static nodes_iterator nodes_end(bolt::BinaryFunction *F) {
     llvm_unreachable("Not implemented");
     return nodes_iterator(F->end());
   }
   static size_t size(bolt::BinaryFunction *F) { return F->size(); }
 };
 
 template <>
 struct GraphTraits<const bolt::BinaryFunction *>
     : public GraphTraits<const bolt::BinaryBasicBlock *> {
   static NodeRef getEntryNode(const bolt::BinaryFunction *F) {
-    return *F->layout_begin();
+    return F->getLayout().block_front();
   }
 
   using nodes_iterator = pointer_iterator<bolt::BinaryFunction::const_iterator>;
 
   static nodes_iterator nodes_begin(const bolt::BinaryFunction *F) {
     llvm_unreachable("Not implemented");
     return nodes_iterator(F->begin());
   }
   static nodes_iterator nodes_end(const bolt::BinaryFunction *F) {
     llvm_unreachable("Not implemented");
     return nodes_iterator(F->end());
   }
   static size_t size(const bolt::BinaryFunction *F) { return F->size(); }
 };
 
 template <>
 struct GraphTraits<Inverse<bolt::BinaryFunction *>>
     : public GraphTraits<Inverse<bolt::BinaryBasicBlock *>> {
   static NodeRef getEntryNode(Inverse<bolt::BinaryFunction *> G) {
-    return *G.Graph->layout_begin();
+    return G.Graph->getLayout().block_front();
   }
 };
 
 template <>
 struct GraphTraits<Inverse<const bolt::BinaryFunction *>>
     : public GraphTraits<Inverse<const bolt::BinaryBasicBlock *>> {
   static NodeRef getEntryNode(Inverse<const bolt::BinaryFunction *> G) {
-    return *G.Graph->layout_begin();
+    return G.Graph->getLayout().block_front();
   }
 };
 
 } // namespace llvm
 
 #endif

bolt/include/bolt/Core/FunctionLayout.h

+//===- bolt/Core/FunctionLayout.h - Fragmented Function Layout --*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the declaration of the FunctionLayout class. The layout of
+// a function is the order of basic blocks, in which we will arrange them in the
+// new binary. Normally, when not optimizing for code layout, the blocks of a
+// function are contiguous. However, we can split the layout into multiple
+// fragments. The blocks within a fragment are contiguous, but the fragments
+// itself are disjoint. Fragments could be used to enhance code layout, e.g. to
+// separate the blocks into hot and cold sections.
+//
+//===----------------------------------------------------------------------===//
+
+#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"
+
+namespace llvm {
+namespace bolt {
+
+class BinaryFunction;
+class BinaryBasicBlock;
+class FunctionLayout;
+
+class FragmentNum {
+  unsigned Value{0};
+
+public:
+  constexpr FragmentNum() = default;
+  constexpr explicit FragmentNum(unsigned Value) : Value(Value) {}
+  constexpr unsigned get() const { return Value; }
+  constexpr bool operator==(const FragmentNum Other) const {
+    return Value == Other.Value;
+  }
+  constexpr bool operator!=(const FragmentNum Other) const {
+    return !(*this == Other);
+  }
+
+  static constexpr FragmentNum hot() { return FragmentNum(0); }
+  static constexpr FragmentNum cold() { return FragmentNum(1); }
+};
+
+/// A freestanding subset of contiguous blocks of a function.
+class FunctionFragment {
+  using BasicBlockListType = SmallVector<BinaryBasicBlock *, 0>;
+  using FragmentListType = SmallVector<unsigned, 0>;
+
+public:
+  using const_iterator = BasicBlockListType::const_iterator;
+
+private:
+  FragmentNum Num;
+  const FunctionLayout &Layout;
+
+  FunctionFragment(FragmentNum Num, const FunctionLayout &Layout)
+      : Num(Num), Layout(Layout) {}
+
+public:
+  unsigned size() const;
+  bool empty() const;
+  const_iterator begin() const;
+  const_iterator end() const;
+  BinaryBasicBlock *front() const;
+
+  friend class FunctionLayout;
+  friend class FragmentIterator;
+};
+
+/// The function layout represents the fragments we split a function into and
+/// the order of basic blocks within each fragment.
+///
+/// Internally, the function layout stores blocks across fragments contiguously.
+/// This is necessary to retain compatibility with existing code and tests that
+/// iterate  over all blocks of the layout and depend on that order. When
+/// writing new code, avoid iterating using FunctionLayout::blocks() by
+/// iterating either over fragments or over BinaryFunction::begin()..end().
+class FunctionLayout {
+private:
+  using BasicBlockListType = SmallVector<BinaryBasicBlock *, 0>;
+  using block_iterator = BasicBlockListType::iterator;
+  using FragmentListType = SmallVector<unsigned, 0>;
+
+public:
+  class FragmentIterator;
+
+  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) {}
+
+  public:
+    bool operator==(const FragmentIterator &Other) const {
+      return Num == Other.Num;
+    }
+
+    FunctionFragment operator*() const {
+      return FunctionFragment(Num, *Layout);
+    }
+
+    FragmentIterator &operator++() {
+      Num = FragmentNum(Num.get() + 1);
+      return *this;
+    }
+
+    FragmentIterator &operator--() {
+      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};
+  BasicBlockListType PreviousBlocks;
+  FragmentListType PreviousFragments;
+
+public:
+  /// Add an empty fragment.
+  FunctionFragment addFragment();
+
+  /// Return the fragment identified by Num.
+  FunctionFragment getFragment(FragmentNum Num) const;
+
+  /// Find the fragment that contains BB.
+  FunctionFragment findFragment(const BinaryBasicBlock *BB) const;
+
+  /// Add BB to the end of the last fragment.
+  void addBasicBlock(BinaryBasicBlock *BB);
+
+  /// Insert range of basic blocks after InsertAfter. If InsertAfter is nullptr,
+  /// the blocks will be inserted at the start of the function.
+  void insertBasicBlocks(BinaryBasicBlock *InsertAfter,
+                         ArrayRef<BinaryBasicBlock *> NewBlocks);
+
+  /// Erase all blocks from the layout that are in ToErase.
+  void eraseBasicBlocks(const DenseSet<const BinaryBasicBlock *> ToErase);
+
+  /// Make sure fragments' and basic blocks' indices match the current layout.
+  void updateLayoutIndices() const;
+
+  /// Replace the current layout with NewLayout. Uses the block's
+  /// self-identifying fragment number to assign blocks to infer function
+  /// fragments.
+  void update(const ArrayRef<BinaryBasicBlock *> NewLayout);
+
+  /// Return true if the layout has been changed by basic block reordering,
+  /// false otherwise.
+  bool hasLayoutChanged() const { return !PreviousBlocks.empty(); }
+
+  /// Clear layout releasing memory.
+  void clear();
+
+  BinaryBasicBlock *getBlock(unsigned Index) const { return Blocks[Index]; }
+
+  /// Returns the basic block after the given basic block in the layout or
+  /// nullptr if the last basic block is given.
+  BinaryBasicBlock *getBasicBlockAfter(const BinaryBasicBlock *BB,
+                                       bool IgnoreSplits = true) const;
+
+  /// 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);
+  }
+
+  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(); }
+  iterator_range<block_const_iterator> blocks() const {
+    return {block_begin(), block_end()};
+  }
+  block_const_reverse_iterator block_rbegin() const { return Blocks.rbegin(); }
+  block_const_reverse_iterator block_rend() const { return Blocks.rend(); }
+  iterator_range<block_const_reverse_iterator> rblocks() const {
+    return {block_rbegin(), block_rend()};
+  }
+
+private:
+  block_const_iterator findBasicBlockPos(const BinaryBasicBlock *BB) const;
+  block_iterator findBasicBlockPos(const BinaryBasicBlock *BB);
+
+  friend class FunctionFragment;
+};
+
+} // namespace bolt
+} // namespace llvm
+
+#endif

bolt/lib/Core/BinaryEmitter.cpp

 
 void BinaryEmitter::emitFunctionBody(BinaryFunction &BF, bool EmitColdPart,
                                      bool EmitCodeOnly) {
   if (!EmitCodeOnly && EmitColdPart && BF.hasConstantIsland())
     BF.duplicateConstantIslands();
 
   // Track the first emitted instruction with debug info.
   bool FirstInstr = true;
-  for (BinaryBasicBlock *BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     if (EmitColdPart != BB->isCold())
       continue;
 
     if ((opts::AlignBlocks || opts::PreserveBlocksAlignment) &&
         BB->getAlignment() > 1)
       Streamer.emitCodeAlignment(BB->getAlignment(), &*BC.STI,
                                  BB->getAlignmentMaxBytes());
     Streamer.emitLabel(BB->getLabel());

bolt/lib/Core/BinaryFunction.cpp

 #include "bolt/Core/MCPlusBuilder.h"
 #include "bolt/Utils/NameResolver.h"
 #include "bolt/Utils/NameShortener.h"
 #include "bolt/Utils/Utils.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
-#include "llvm/ADT/edit_distance.h"
 #include "llvm/Demangle/Demangle.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCAsmLayout.h"
 #include "llvm/MC/MCContext.h"
 #include "llvm/MC/MCDisassembler/MCDisassembler.h"
 #include "llvm/MC/MCExpr.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/MC/MCInstPrinter.h"
for (BinaryBasicBlock *Succ : BB->successors()) {
       Stack.push(Succ);
     }
   }
 }
 
 // Any unnecessary fallthrough jumps revealed after calling eraseInvalidBBs
 // will be cleaned up by fixBranches().
 std::pair<unsigned, uint64_t> BinaryFunction::eraseInvalidBBs() {
-  BasicBlockOrderType NewLayout;
+  DenseSet<const BinaryBasicBlock *> InvalidBBs;
   unsigned Count = 0;
   uint64_t Bytes = 0;
-  for (BinaryBasicBlock *BB : layout()) {
-    if (BB->isValid()) {
-      NewLayout.push_back(BB);
-    } else {
+  for (BinaryBasicBlock *const BB : BasicBlocks) {
+    if (!BB->isValid()) {
       assert(!isEntryPoint(*BB) && "all entry blocks must be valid");
+      InvalidBBs.insert(BB);
       ++Count;
       Bytes += BC.computeCodeSize(BB->begin(), BB->end());
     }
   }
-  BasicBlocksLayout = std::move(NewLayout);
+
+  Layout.eraseBasicBlocks(InvalidBBs);
 
   BasicBlockListType NewBasicBlocks;
   for (auto I = BasicBlocks.begin(), E = BasicBlocks.end(); I != E; ++I) {
     BinaryBasicBlock *BB = *I;
-    if (BB->isValid()) {
-      NewBasicBlocks.push_back(BB);
-    } else {
+    if (InvalidBBs.contains(BB)) {
       // Make sure the block is removed from the list of predecessors.
       BB->removeAllSuccessors();
       DeletedBasicBlocks.push_back(BB);
+    } else {
+      NewBasicBlocks.push_back(BB);
     }
   }
   BasicBlocks = std::move(NewBasicBlocks);
 
-  assert(BasicBlocks.size() == BasicBlocksLayout.size());
+  assert(BasicBlocks.size() == Layout.block_size());
 
   // Update CFG state if needed
   if (Count > 0)
     recomputeLandingPads();
 
   return std::make_pair(Count, Bytes);
 }
 
void BinaryFunction::print(raw_ostream &OS, std::string Annotation,
   if (isMultiEntry()) {
     OS << "\n  Secondary Entry Points : ";
     ListSeparator LS;
     for (const auto &KV : SecondaryEntryPoints)
       OS << LS << KV.second->getName();
   }
   if (FrameInstructions.size())
     OS << "\n  CFI Instrs  : " << FrameInstructions.size();
-  if (BasicBlocksLayout.size()) {
+  if (!Layout.block_empty()) {
     OS << "\n  BB Layout   : ";
     ListSeparator LS;
-    for (BinaryBasicBlock *BB : BasicBlocksLayout)
+    for (const BinaryBasicBlock *BB : Layout.blocks())
       OS << LS << BB->getName();
   }
   if (ImageAddress)
     OS << "\n  Image       : 0x" << Twine::utohexstr(ImageAddress);
   if (ExecutionCount != COUNT_NO_PROFILE) {
     OS << "\n  Exec Count  : " << ExecutionCount;
     OS << "\n  Profile Acc : " << format("%.1f%%", ProfileMatchRatio * 100.0f);
   }
 
-  if (opts::PrintDynoStats && !BasicBlocksLayout.empty()) {
+  if (opts::PrintDynoStats && !getLayout().block_empty()) {
     OS << '\n';
     DynoStats dynoStats = getDynoStats(*this);
     OS << dynoStats;
   }
 
   OS << "\n}\n";
 
   if (opts::PrintDynoStatsOnly || !PrintInstructions || !BC.InstPrinter)
for (const std::pair<const uint32_t, MCInst> &II : Instructions) {
           OS << EntrySymbol->getName() << " (Entry Point):\n";
         OS << LI->second->getName() << ":\n";
       }
 
       BC.printInstruction(OS, II.second, Offset, this);
     }
   }
 
-  for (uint32_t I = 0, E = BasicBlocksLayout.size(); I != E; ++I) {
-    BinaryBasicBlock *BB = BasicBlocksLayout[I];
-    if (I != 0 && BB->isCold() != BasicBlocksLayout[I - 1]->isCold())
-      OS << "-------   HOT-COLD SPLIT POINT   -------\n\n";
-
+  StringRef SplitPointMsg = "";
+  for (const FunctionFragment F : Layout) {
+    OS << SplitPointMsg;
+    SplitPointMsg = "-------   HOT-COLD SPLIT POINT   -------\n\n";
+    for (const BinaryBasicBlock *BB : F) {
       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";
       }
 
       if (BB->isLandingPad())
         OS << "  Landing Pad\n";
 
       uint64_t BBExecCount = BB->getExecutionCount();
       if (hasValidProfile()) {
         OS << "  Exec Count : ";
         if (BB->getExecutionCount() != BinaryBasicBlock::COUNT_NO_PROFILE)
           OS << BBExecCount << '\n';
         else
           OS << "<unknown>\n";
       }
       if (BB->getCFIState() >= 0)
         OS << "  CFI State : " << BB->getCFIState() << '\n';
       if (opts::EnableBAT) {
         OS << "  Input offset: " << Twine::utohexstr(BB->getInputOffset())
            << "\n";
       }
       if (!BB->pred_empty()) {
         OS << "  Predecessors: ";
         ListSeparator LS;
         for (BinaryBasicBlock *Pred : BB->predecessors())
           OS << LS << Pred->getName();
         OS << '\n';
       }
       if (!BB->throw_empty()) {
         OS << "  Throwers: ";
         ListSeparator LS;
         for (BinaryBasicBlock *Throw : BB->throwers())
           OS << LS << Throw->getName();
         OS << '\n';
       }
 
       Offset = alignTo(Offset, BB->getAlignment());
 
-    // Note: offsets are imprecise since this is happening prior to relaxation.
+      // Note: offsets are imprecise since this is happening prior to
+      // relaxation.
       Offset = BC.printInstructions(OS, BB->begin(), BB->end(), Offset, this);
 
       if (!BB->succ_empty()) {
         OS << "  Successors: ";
         // For more than 2 successors, sort them based on frequency.
         std::vector<uint64_t> Indices(BB->succ_size());
         std::iota(Indices.begin(), Indices.end(), 0);
         if (BB->succ_size() > 2 && BB->getKnownExecutionCount()) {
           llvm::stable_sort(Indices, [&](const uint64_t A, const uint64_t B) {
             return BB->BranchInfo[B] < BB->BranchInfo[A];
           });
         }
         ListSeparator LS;
         for (unsigned I = 0; I < Indices.size(); ++I) {
           BinaryBasicBlock *Succ = BB->Successors[Indices[I]];
-        BinaryBasicBlock::BinaryBranchInfo &BI = BB->BranchInfo[Indices[I]];
+          const BinaryBasicBlock::BinaryBranchInfo &BI =
+              BB->BranchInfo[Indices[I]];
           OS << LS << Succ->getName();
           if (ExecutionCount != COUNT_NO_PROFILE &&
               BI.MispredictedCount != BinaryBasicBlock::COUNT_INFERRED) {
             OS << " (mispreds: " << BI.MispredictedCount
                << ", count: " << BI.Count << ")";
           } else if (ExecutionCount != COUNT_NO_PROFILE &&
                      BI.Count != BinaryBasicBlock::COUNT_NO_PROFILE) {
             OS << " (inferred count: " << BI.Count << ")";
           }
         }
         OS << '\n';
       }
 
       if (!BB->lp_empty()) {
         OS << "  Landing Pads: ";
         ListSeparator LS;
         for (BinaryBasicBlock *LP : BB->landing_pads()) {
           OS << LS << LP->getName();
           if (ExecutionCount != COUNT_NO_PROFILE) {
             OS << " (count: " << LP->getExecutionCount() << ")";
           }
         }
         OS << '\n';
       }
 
       // In CFG_Finalized state we can miscalculate CFI state at exit.
       if (CurrentState == State::CFG) {
         const int32_t CFIStateAtExit = BB->getCFIStateAtExit();
         if (CFIStateAtExit >= 0)
           OS << "  CFI State: " << CFIStateAtExit << '\n';
       }
 
       OS << '\n';
     }
+  }
 
   // Dump new exception ranges for the function.
   if (!CallSites.empty()) {
     OS << "EH table:\n";
     for (const CallSite &CSI : CallSites) {
       OS << "  [" << *CSI.Start << ", " << *CSI.End << ") landing pad : ";
       if (CSI.LP)
         OS << *CSI.LP;
bool BinaryFunction::buildCFG(MCPlusBuilder::AllocatorIdTy AllocatorId) {
   annotateCFIState();
 
   // Annotate invoke instructions with GNU_args_size data.
   propagateGnuArgsSizeInfo(AllocatorId);
 
   // Set the basic block layout to the original order and set end offsets.
   PrevBB = nullptr;
   for (BinaryBasicBlock *BB : BasicBlocks) {
-    BasicBlocksLayout.emplace_back(BB);
+    Layout.addBasicBlock(BB);
     if (PrevBB)
       PrevBB->setEndOffset(BB->getOffset());
     PrevBB = BB;
   }
   PrevBB->setEndOffset(getSize());
 
-  updateLayoutIndices();
+  Layout.updateLayoutIndices();
 
   normalizeCFIState();
 
   // Clean-up memory taken by intermediate structures.
   //
   // NB: don't clear Labels list as we may need them if we mark the function
   //     as non-simple later in the process of discovering extra entry points.
   clearList(Instructions);

 
 void BinaryFunction::normalizeCFIState() {
   // Reordering blocks with remember-restore state instructions can be specially
   // tricky. When rewriting the CFI, we omit remember-restore state instructions
   // entirely. For restore state, we build a map expanding each restore to the
   // equivalent unwindCFIState sequence required at that point to achieve the
   // same effect of the restore. All remember state are then just ignored.
   std::stack<int32_t> Stack;
-  for (BinaryBasicBlock *CurBB : BasicBlocksLayout) {
+  for (BinaryBasicBlock *CurBB : Layout.blocks()) {
     for (auto II = CurBB->begin(); II != CurBB->end(); ++II) {
       if (const MCCFIInstruction *CFI = getCFIFor(*II)) {
         if (CFI->getOperation() == MCCFIInstruction::OpRememberState) {
           Stack.push(II->getOperand(0).getImm());
           continue;
         }
         if (CFI->getOperation() == MCCFIInstruction::OpRestoreState) {
           const int32_t RememberState = Stack.top();
           const int32_t CurState = II->getOperand(0).getImm();
           FrameRestoreEquivalents[CurState] =
               unwindCFIState(CurState, RememberState, CurBB, II);
           Stack.pop();
         }
       }
     }
   }
 }
 
 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
                     << ": ");
 
-  int32_t State = 0;
-  bool SeenCold = false;
   const char *Sep = "";
   (void)Sep;
-  for (BinaryBasicBlock *BB : BasicBlocksLayout) {
-    const int32_t CFIStateAtExit = BB->getCFIStateAtExit();
+  for (const FunctionFragment F : Layout) {
+    // Hot-cold border: at start of each region (with a different FDE) we need
+    // to reset the CFI state.
+    int32_t State = 0;
 
-    // Hot-cold border: check if this is the first BB to be allocated in a cold
-    // region (with a different FDE). If yes, we need to reset the CFI state.
-    if (!SeenCold && BB->isCold()) {
-      State = 0;
-      SeenCold = true;
-    }
+    for (BinaryBasicBlock *BB : F) {
+      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.
         auto InsertIt = BB->begin();
         unwindCFIState(State, BB->getCFIState(), BB, InsertIt);
       } else if (BB->getCFIState() > State) {
-      // If BB's CFI state is greater than State, it means we are behind in the
-      // state. Just emit all instructions to reach this state at the
+        // If BB's CFI state is greater than State, it means we are behind in
+        // the state. Just emit all instructions to reach this state at the
         // beginning of this BB. If this sequence of instructions involve
         // remember state or restore state, bail out.
         if (!replayCFIInstrs(State, BB->getCFIState(), BB, BB->begin()))
           return false;
       }
 
       State = CFIStateAtExit;
       LLVM_DEBUG(dbgs() << Sep << State; Sep = ", ");
     }
+  }
   LLVM_DEBUG(dbgs() << "\n");
 
   for (BinaryBasicBlock &BB : blocks()) {
     for (auto II = BB.begin(); II != BB.end();) {
       const MCCFIInstruction *CFI = getCFIFor(*II);
       if (CFI && (CFI->getOperation() == MCCFIInstruction::OpRememberState ||
                   CFI->getOperation() == MCCFIInstruction::OpRestoreState)) {
         II = BB.eraseInstruction(II);

 
 uint64_t BinaryFunction::getInstructionCount() const {
   uint64_t Count = 0;
   for (const BinaryBasicBlock &BB : blocks())
     Count += BB.getNumNonPseudos();
   return Count;
 }
 
-bool BinaryFunction::hasLayoutChanged() const { return ModifiedLayout; }
-
-uint64_t BinaryFunction::getEditDistance() const {
-  return ComputeEditDistance<BinaryBasicBlock *>(BasicBlocksPreviousLayout,
-                                                 BasicBlocksLayout);
-}
-
 void BinaryFunction::clearDisasmState() {
   clearList(Instructions);
   clearList(IgnoredBranches);
   clearList(TakenBranches);
 
   if (BC.HasRelocations) {
     for (std::pair<const uint32_t, MCSymbol *> &LI : Labels)
       BC.UndefinedSymbols.insert(LI.second);
if (hasCFG()) {
     for (BinaryBasicBlock *BB : BasicBlocks)
       delete BB;
     clearList(BasicBlocks);
 
     for (BinaryBasicBlock *BB : DeletedBasicBlocks)
       delete BB;
     clearList(DeletedBasicBlocks);
 
-    clearList(BasicBlocksLayout);
-    clearList(BasicBlocksPreviousLayout);
+    Layout.clear();
   }
 
   CurrentState = State::Empty;
 
   IsIgnored = true;
   IsSimple = false;
   LLVM_DEBUG(dbgs() << "Ignoring " << getPrintName() << '\n');
 }
 
 void BinaryFunction::duplicateConstantIslands() {
   assert(Islands && "function expected to have constant islands");
 
-  for (BinaryBasicBlock *BB : layout()) {
+  for (BinaryBasicBlock *BB : getLayout().blocks()) {
     if (!BB->isCold())
       continue;
 
     for (MCInst &Inst : *BB) {
       int OpNum = 0;
       for (MCOperand &Operand : Inst) {
         if (!Operand.isExpr()) {
           ++OpNum;

 
 } // namespace
 
 void BinaryFunction::dumpGraph(raw_ostream &OS) const {
   OS << "digraph \"" << getPrintName() << "\" {\n"
      << "node [fontname=courier, shape=box, style=filled, colorscheme=brbg9]\n";
   uint64_t Offset = Address;
   for (BinaryBasicBlock *BB : BasicBlocks) {
-    auto LayoutPos = llvm::find(BasicBlocksLayout, BB);
-    unsigned Layout = LayoutPos - BasicBlocksLayout.begin();
+    auto LayoutPos = find(Layout.blocks(), BB);
+    unsigned LayoutIndex = LayoutPos - Layout.block_begin();
     const char *ColdStr = BB->isCold() ? " (cold)" : "";
     std::vector<std::string> Attrs;
     // Bold box for entry points
     if (isEntryPoint(*BB))
       Attrs.push_back("penwidth=2");
     if (BLI && BLI->getLoopFor(BB)) {
       // Distinguish innermost loops
       const BinaryLoop *Loop = BLI->getLoopFor(BB);
       if (Loop->isInnermost())
         Attrs.push_back("fillcolor=6");
       else // some outer loop
         Attrs.push_back("fillcolor=4");
     } else { // non-loopy code
       Attrs.push_back("fillcolor=5");
     }
     ListSeparator LS;
     OS << "\"" << BB->getName() << "\" [";
     for (StringRef Attr : Attrs)
       OS << LS << Attr;
     OS << "]\n";
     OS << format("\"%s\" [label=\"%s%s\\n(C:%lu,O:%lu,I:%u,L:%u,CFI:%u)\\n",
                  BB->getName().data(), BB->getName().data(), ColdStr,
                  BB->getKnownExecutionCount(), BB->getOffset(), getIndex(BB),
-                 Layout, BB->getCFIState());
+                 LayoutIndex, BB->getCFIState());
 
     if (opts::DotToolTipCode) {
       std::string Str;
       raw_string_ostream CS(Str);
       Offset = BC.printInstructions(CS, BB->begin(), BB->end(), Offset, this,
                                     /* PrintMCInst = */ false,
                                     /* PrintMemData = */ false,
                                     /* PrintRelocations = */ false,
bool BinaryFunction::validateCFG() const {
 
   return Valid;
 }
 
 void BinaryFunction::fixBranches() {
   auto &MIB = BC.MIB;
   MCContext *Ctx = BC.Ctx.get();
 
-  for (unsigned I = 0, E = BasicBlocksLayout.size(); I != E; ++I) {
-    BinaryBasicBlock *BB = BasicBlocksLayout[I];
+  for (BinaryBasicBlock *BB : BasicBlocks) {
     const MCSymbol *TBB = nullptr;
     const MCSymbol *FBB = nullptr;
     MCInst *CondBranch = nullptr;
     MCInst *UncondBranch = nullptr;
     if (!BB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch))
       continue;
 
     // We will create unconditional branch with correct destination if needed.
     if (UncondBranch)
       BB->eraseInstruction(BB->findInstruction(UncondBranch));
 
     // Basic block that follows the current one in the final layout.
-    const BinaryBasicBlock *NextBB = nullptr;
-    if (I + 1 != E && BB->isCold() == BasicBlocksLayout[I + 1]->isCold())
-      NextBB = BasicBlocksLayout[I + 1];
+    const BinaryBasicBlock *NextBB =
+        Layout.getBasicBlockAfter(BB, /*IgnoreSplits=*/false);
 
     if (BB->succ_size() == 1) {
       // __builtin_unreachable() could create a conditional branch that
       // falls-through into the next function - hence the block will have only
       // one valid successor. Since behaviour is undefined - we replace
       // the conditional branch with an unconditional if required.
       if (CondBranch)
         BB->eraseInstruction(BB->findInstruction(CondBranch));

 
 size_t BinaryFunction::computeHash(bool UseDFS,
                                    OperandHashFuncTy OperandHashFunc) const {
   if (size() == 0)
     return 0;
 
   assert(hasCFG() && "function is expected to have CFG");
 
-  const BasicBlockOrderType &Order = UseDFS ? dfs() : BasicBlocksLayout;
+  BasicBlockListType Order;
+  if (UseDFS)
+    Order = dfs();
+  else
+    llvm::copy(Layout.blocks(), std::back_inserter(Order));
 
   // The hash is computed by creating a string of all instruction opcodes and
   // possibly their operands and then hashing that string with std::hash.
   std::string HashString;
   for (const BinaryBasicBlock *BB : Order) {
     for (const MCInst &Inst : *BB) {
       unsigned Opcode = Inst.getOpcode();
 
void BinaryFunction::updateCFIState(BinaryBasicBlock *Start,
   const int32_t CFIState = Start->getCFIStateAtExit();
   const unsigned StartIndex = getIndex(Start) + 1;
   for (unsigned I = 0; I < NumNewBlocks; ++I)
     BasicBlocks[StartIndex + I]->setCFIState(CFIState);
 }
 
 void BinaryFunction::updateLayout(BinaryBasicBlock *Start,
                                   const unsigned NumNewBlocks) {
-  // If start not provided insert new blocks at the beginning
+  BasicBlockListType::iterator Begin;
+  BasicBlockListType::iterator End;
+
+  // If start not provided copy new blocks from the beginning of BasicBlocks
   if (!Start) {
-    BasicBlocksLayout.insert(layout_begin(), BasicBlocks.begin(),
-                             BasicBlocks.begin() + NumNewBlocks);
-    updateLayoutIndices();
-    return;
+    Begin = BasicBlocks.begin();
+    End = BasicBlocks.begin() + NumNewBlocks;
+  } else {
+    unsigned StartIndex = getIndex(Start);
+    Begin = std::next(BasicBlocks.begin(), StartIndex + 1);
+    End = std::next(BasicBlocks.begin(), StartIndex + NumNewBlocks + 1);
   }
 
   // Insert new blocks in the layout immediately after Start.
-  auto Pos = llvm::find(layout(), Start);
-  assert(Pos != layout_end());
-  BasicBlockListType::iterator Begin =
-      std::next(BasicBlocks.begin(), getIndex(Start) + 1);
-  BasicBlockListType::iterator End =
-      std::next(BasicBlocks.begin(), getIndex(Start) + NumNewBlocks + 1);
-  BasicBlocksLayout.insert(Pos + 1, Begin, End);
-  updateLayoutIndices();
+  Layout.insertBasicBlocks(Start, {Begin, End});
+  Layout.updateLayoutIndices();
 }
 
 bool BinaryFunction::checkForAmbiguousJumpTables() {
   SmallSet<uint64_t, 4> JumpTables;
   for (BinaryBasicBlock *&BB : BasicBlocks) {
     for (MCInst &Inst : *BB) {
       if (!BC.MIB->isIndirectBranch(Inst))
         continue;
if (!opts::UpdateDebugSections && !isMultiEntry() &&
       !requiresAddressTranslation())
     return;
 
   // Output ranges should match the input if the body hasn't changed.
   if (!isSimple() && !BC.HasRelocations)
     return;
 
   // AArch64 may have functions that only contains a constant island (no code).
-  if (layout_begin() == layout_end())
+  if (getLayout().block_empty())
     return;
 
   BinaryBasicBlock *PrevBB = nullptr;
-  for (auto BBI = layout_begin(), BBE = layout_end(); BBI != BBE; ++BBI) {
-    BinaryBasicBlock *BB = *BBI;
+  for (BinaryBasicBlock *BB : this->Layout.blocks()) {
     assert(BB->getLabel()->isDefined() && "symbol should be defined");
     const uint64_t BBBaseAddress = BB->isCold() ? ColdBaseAddress : BaseAddress;
     if (!BC.HasRelocations) {
       if (BB->isCold()) {
         assert(BBBaseAddress == cold().getAddress());
       } else {
         assert(BBBaseAddress == getOutputAddress());
       }

bolt/lib/Core/CMakeLists.txt

add_llvm_library(LLVMBOLTCore
   BinaryData.cpp
   BinaryEmitter.cpp
   BinaryFunction.cpp
   BinaryFunctionProfile.cpp
   BinarySection.cpp
   DebugData.cpp
   DynoStats.cpp
   Exceptions.cpp
+  FunctionLayout.cpp
   JumpTable.cpp
   MCPlusBuilder.cpp
   ParallelUtilities.cpp
   Relocation.cpp
 
   LINK_LIBS
   ${LLVM_PTHREAD_LIB}
   )
 
 target_link_libraries(LLVMBOLTCore
   PRIVATE
   LLVMBOLTUtils
   )

bolt/lib/Core/DynoStats.cpp

DynoStats getDynoStats(const BinaryFunction &BF) {
   DynoStats Stats(/*PrintAArch64Stats*/ BC.isAArch64());
 
   // Return empty-stats about the function we don't completely understand.
   if (!BF.isSimple() || !BF.hasValidProfile() || !BF.hasCanonicalCFG())
     return Stats;
 
   // Update enumeration of basic blocks for correct detection of branch'
   // direction.
-  BF.updateLayoutIndices();
+  BF.getLayout().updateLayoutIndices();
 
-  for (BinaryBasicBlock *const &BB : BF.layout()) {
+  for (BinaryBasicBlock *const BB : BF.getLayout().blocks()) {
     // The basic block execution count equals to the sum of incoming branch
     // frequencies. This may deviate from the sum of outgoing branches of the
     // basic block especially since the block may contain a function that
     // does not return or a function that throws an exception.
     const uint64_t BBExecutionCount = BB->getKnownExecutionCount();
 
     // Ignore empty blocks and blocks that were not executed.
     if (BB->getNumNonPseudos() == 0 || BBExecutionCount == 0)

bolt/lib/Core/Exceptions.cpp

void BinaryFunction::updateEHRanges() {
   bool IsStartInCold = false;
 
   // Have we crossed hot/cold border for split functions?
   bool SeenCold = false;
 
   // Sites to update - either regular or cold.
   CallSitesType *Sites = &CallSites;
 
-  for (BinaryBasicBlock *&BB : BasicBlocksLayout) {
+  for (BinaryBasicBlock *BB : getLayout().blocks()) {
 
     if (BB->isCold() && !SeenCold) {
       SeenCold = true;
 
       // Close the range (if any) and change the target call sites.
       if (StartRange) {
         Sites->emplace_back(CallSite{StartRange, getFunctionEndLabel(),
                                      PreviousEH.LP, PreviousEH.Action});

bolt/lib/Core/FunctionLayout.cpp

+#include "bolt/Core/FunctionLayout.h"
+#include "bolt/Core/BinaryFunction.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/edit_distance.h"
+#include <algorithm>
+#include <functional>
+
+using namespace llvm;
+using namespace bolt;
+
+unsigned FunctionFragment::size() const { return end() - begin(); }
+bool FunctionFragment::empty() const { return end() == begin(); }
+FunctionFragment::const_iterator FunctionFragment::begin() const {
+  return Layout.block_begin() + Layout.Fragments[Num.get()];
+}
+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();
+}
+
+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;
+    NewFragments.emplace_back(NewFragment);
+  }
+  Blocks.erase(std::remove_if(Blocks.begin(), Blocks.end(), IsErased),
+               Blocks.end());
+  Fragments = std::move(NewFragments);
+}
+
+void FunctionLayout::updateLayoutIndices() const {
+  unsigned BlockIndex = 0;
+  for (const FunctionFragment F : *this) {
+    for (BinaryBasicBlock *const BB : F)
+      BB->setLayoutIndex(BlockIndex++);
+  }
+}
+
+void FunctionLayout::update(const ArrayRef<BinaryBasicBlock *> NewLayout) {
+  PreviousBlocks = std::move(Blocks);
+  PreviousFragments = std::move(Fragments);
+
+  Blocks.clear();
+  Fragments = {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() &&
+           "Blocks must be arranged such that fragments are monotonically "
+           "increasing.");
+
+    // Add empty fragments if necessary
+    for (unsigned I = 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};
+  PreviousBlocks = {};
+  PreviousFragments = {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(); });
+  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);
+}

bolt/lib/Passes/Aligner.cpp

void AlignerPass::alignBlocks(BinaryFunction &Function,
   if (!Function.hasValidProfile() || !Function.isSimple())
     return;
 
   const BinaryContext &BC = Function.getBinaryContext();
 
   const uint64_t FuncCount =
       std::max<uint64_t>(1, Function.getKnownExecutionCount());
   BinaryBasicBlock *PrevBB = nullptr;
-  for (BinaryBasicBlock *BB : Function.layout()) {
+  for (BinaryBasicBlock *BB : Function.getLayout().blocks()) {
     uint64_t Count = BB->getKnownExecutionCount();
 
     if (Count <= FuncCount * opts::AlignBlocksThreshold / 100) {
       PrevBB = BB;
       continue;
     }
 
     uint64_t FTCount = 0;

bolt/lib/Passes/AsmDump.cpp

OS << "# FDATA: 0 [unknown] 0 "
        << "0 " << EntryExecCount << '\n';
 
   // Binary data references from the function.
   std::unordered_set<const BinaryData *> BDReferences;
   // Function references from the function (to avoid constructing call graph).
   std::unordered_set<const MCSymbol *> CallReferences;
 
   MAP->OutStreamer->emitCFIStartProc(/*IsSimple=*/false);
-  for (BinaryBasicBlock *BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     OS << BB->getName() << ": \n";
 
     const std::string BranchLabel = Twine(BB->getName(), "_br").str();
     const MCInst *LastInst = BB->getLastNonPseudoInstr();
 
     for (const MCInst &Instr : *BB) {
       // Dump pseudo instructions (CFI)
       if (BC.MIB->isPseudo(Instr)) {

bolt/lib/Passes/BinaryFunctionCallGraph.cpp

if (!Function->hasValidProfile() && CgFromPerfData &&
         Offset = CSI.Offset;
         if (Offset > Size)
           Offset = Size;
 
         if (!recordCall(CSI.Symbol, CSI.Count))
           ++NotProcessed;
       }
     } else {
-      for (BinaryBasicBlock *BB : Function->layout()) {
+      for (BinaryBasicBlock *BB : Function->getLayout().blocks()) {
         // Don't count calls from cold blocks unless requested.
         if (BB->isCold() && !IncludeColdCalls)
           continue;
 
         // Determine whether the block is included in Function's (hot) size
         // See BinaryFunction::estimateHotSize
         bool BBIncludedInFunctionSize = false;
         if (UseFunctionHotSize && Function->isSplit()) {

bolt/lib/Passes/BinaryPasses.cpp

outs() << "BOLT-INFO: removed " << NumBlocksRemoved << " empty block"
            << (NumBlocksRemoved == 1 ? "" : "s") << '\n';
   if (NumDuplicateEdgesMerged)
     outs() << "BOLT-INFO: merged " << NumDuplicateEdgesMerged
            << " duplicate CFG edge" << (NumDuplicateEdgesMerged == 1 ? "" : "s")
            << '\n';
 }
 
 void EliminateUnreachableBlocks::runOnFunction(BinaryFunction &Function) {
-  if (Function.layout_size() > 0) {
+  if (!Function.getLayout().block_empty()) {
     unsigned Count;
     uint64_t Bytes;
     Function.markUnreachableBlocks();
     LLVM_DEBUG({
       for (BinaryBasicBlock &BB : Function) {
         if (!BB.isValid()) {
           dbgs() << "BOLT-INFO: UCE found unreachable block " << BB.getName()
                  << " in function " << Function << "\n";

 void ReorderBasicBlocks::runOnFunctions(BinaryContext &BC) {
   if (opts::ReorderBlocks == ReorderBasicBlocks::LT_NONE)
     return;
 
   std::atomic<uint64_t> ModifiedFuncCount{0};
 
   ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {
     modifyFunctionLayout(BF, opts::ReorderBlocks, opts::MinBranchClusters);
-    if (BF.hasLayoutChanged())
+    if (BF.getLayout().hasLayoutChanged())
       ++ModifiedFuncCount;
   };
 
   ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {
     return !shouldOptimize(BF);
   };
 
   ParallelUtilities::runOnEachFunction(
for (std::map<uint64_t, BinaryFunction &>::reverse_iterator Rit =
       OS << "           Information for function of top: " << (I + 1) << ": \n";
       OS << "             Function Score is: " << Function.getFunctionScore()
          << "\n";
       OS << "             There are " << Function.size()
          << " number of blocks in this function.\n";
       OS << "             There are " << Function.getInstructionCount()
          << " number of instructions in this function.\n";
       OS << "             The edit distance for this function is: "
-         << Function.getEditDistance() << "\n\n";
+         << Function.getLayout().getEditDistance() << "\n\n";
     }
   }
 }
 
 void ReorderBasicBlocks::modifyFunctionLayout(BinaryFunction &BF,
                                               LayoutType Type,
                                               bool MinBranchClusters) const {
   if (BF.size() == 0 || Type == LT_NONE)
if (Type == LT_REVERSE) {
 
     default:
       llvm_unreachable("unexpected layout type");
     }
   }
 
   Algo->reorderBasicBlocks(BF, NewLayout);
 
-  BF.updateBasicBlockLayout(NewLayout);
+  BF.getLayout().update(NewLayout);
 }
 
 void FixupBranches::runOnFunctions(BinaryContext &BC) {
   for (auto &It : BC.getBinaryFunctions()) {
     BinaryFunction &Function = It.second;
     if (!BC.shouldEmit(Function) || !Function.isSimple())
       continue;
 
void LowerAnnotations::runOnFunctions(BinaryContext &BC) {
 
   for (auto &It : BC.getBinaryFunctions()) {
     BinaryFunction &BF = It.second;
     int64_t CurrentGnuArgsSize = 0;
 
     // Have we crossed hot/cold border for split functions?
     bool SeenCold = false;
 
-    for (BinaryBasicBlock *BB : BF.layout()) {
+    for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
       if (BB->isCold() && !SeenCold) {
         SeenCold = true;
         CurrentGnuArgsSize = 0;
       }
 
       // First convert GnuArgsSize annotations into CFIs. This may change instr
       // pointers, so do it before recording ptrs for preserved annotations
       if (BF.usesGnuArgsSize()) {
auto checkAndPatch = [&](BinaryBasicBlock *Pred, BinaryBasicBlock *Succ,
         assert((CondBranch || (!CondBranch && Pred->succ_size() == 1)) &&
                "Predecessor block has inconsistent number of successors");
         if (CondBranch && MIB->getTargetSymbol(*CondBranch) == BB.getLabel()) {
           MIB->replaceBranchTarget(*CondBranch, Succ->getLabel(), Ctx);
         } else if (UncondBranch &&
                    MIB->getTargetSymbol(*UncondBranch) == BB.getLabel()) {
           MIB->replaceBranchTarget(*UncondBranch, Succ->getLabel(), Ctx);
         } else if (!UncondBranch) {
-          assert(Function.getBasicBlockAfter(Pred, false) != Succ &&
+          assert(Function.getLayout().getBasicBlockAfter(Pred, false) != Succ &&
                  "Don't add an explicit jump to a fallthrough block.");
           Pred->addBranchInstruction(Succ);
         }
       } else {
         // Succ will be null in the tail call case.  In this case we
         // need to explicitly add a tail call instruction.
         MCInst *Branch = Pred->getLastNonPseudoInstr();
         if (Branch && MIB->isUnconditionalBranch(*Branch)) {
bool SimplifyConditionalTailCalls::shouldRewriteBranch(
   const bool Result = (IsForward && Frequency.get().first >= 0.5) ||
                       (!IsForward && Frequency.get().first <= 0.5);
 
   return Result == DirectionFlag;
 }
 
 uint64_t SimplifyConditionalTailCalls::fixTailCalls(BinaryFunction &BF) {
   // Need updated indices to correctly detect branch' direction.
-  BF.updateLayoutIndices();
+  BF.getLayout().updateLayoutIndices();
   BF.markUnreachableBlocks();
 
   MCPlusBuilder *MIB = BF.getBinaryContext().MIB.get();
   MCContext *Ctx = BF.getBinaryContext().Ctx.get();
   uint64_t NumLocalCTCCandidates = 0;
   uint64_t NumLocalCTCs = 0;
   uint64_t LocalCTCTakenCount = 0;
   uint64_t LocalCTCExecCount = 0;
   std::vector<std::pair<BinaryBasicBlock *, const BinaryBasicBlock *>>
       NeedsUncondBranch;
 
   // Will block be deleted by UCE?
   auto isValid = [](const BinaryBasicBlock *BB) {
     return (BB->pred_size() != 0 || BB->isLandingPad() || BB->isEntryPoint());
   };
 
-  for (BinaryBasicBlock *BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     // Locate BB with a single direct tail-call instruction.
     if (BB->getNumNonPseudos() != 1)
       continue;
 
     MCInst *Instr = BB->getFirstNonPseudoInstr();
     if (!MIB->isTailCall(*Instr) || MIB->isConditionalBranch(*Instr))
       continue;
 
for (auto &Entry : NeedsUncondBranch) {
     const MCSymbol *TBB = nullptr;
     const MCSymbol *FBB = nullptr;
     MCInst *CondBranch = nullptr;
     MCInst *UncondBranch = nullptr;
     PredBB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch);
 
     // Find the next valid block.  Invalid blocks will be deleted
     // so they shouldn't be considered fallthrough targets.
-    const BinaryBasicBlock *NextBlock = BF.getBasicBlockAfter(PredBB, false);
+    const BinaryBasicBlock *NextBlock =
+        BF.getLayout().getBasicBlockAfter(PredBB, false);
     while (NextBlock && !isValid(NextBlock))
-      NextBlock = BF.getBasicBlockAfter(NextBlock, false);
+      NextBlock = BF.getLayout().getBasicBlockAfter(NextBlock, false);
 
     // Get the unconditional successor to this block.
     const BinaryBasicBlock *PredSucc = PredBB->getSuccessor();
     assert(PredSucc && "The other branch should be a tail call");
 
     const bool HasFallthrough = (NextBlock && PredSucc == NextBlock);
 
     if (UncondBranch) {
bool SimplifyRODataLoads::simplifyRODataLoads(BinaryFunction &BF) {
   BinaryContext &BC = BF.getBinaryContext();
   MCPlusBuilder *MIB = BC.MIB.get();
 
   uint64_t NumLocalLoadsSimplified = 0;
   uint64_t NumDynamicLocalLoadsSimplified = 0;
   uint64_t NumLocalLoadsFound = 0;
   uint64_t NumDynamicLocalLoadsFound = 0;
 
-  for (BinaryBasicBlock *BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     for (MCInst &Inst : *BB) {
       unsigned Opcode = Inst.getOpcode();
       const MCInstrDesc &Desc = BC.MII->get(Opcode);
 
       // Skip instructions that do not load from memory.
       if (!Desc.mayLoad())
         continue;
 
if (opts::ReportBadLayout) {
     for (auto &BFI : BC.getBinaryFunctions()) {
       const BinaryFunction &BF = BFI.second;
       if (!BF.hasValidProfile())
         continue;
 
       const uint64_t HotThreshold =
           std::max<uint64_t>(BF.getKnownExecutionCount(), 1);
       bool HotSeen = false;
-      for (const BinaryBasicBlock *BB : BF.rlayout()) {
+      for (const BinaryBasicBlock *BB : BF.getLayout().rblocks()) {
         if (!HotSeen && BB->getKnownExecutionCount() > HotThreshold) {
           HotSeen = true;
           continue;
         }
         if (HotSeen && BB->getKnownExecutionCount() == 0) {
           SuboptimalFuncs.push_back(&BF);
           break;
         }

bolt/lib/Passes/CacheMetrics.cpp

 /// Build a simplified version of the call graph: For every function, keep
 /// its callers and the frequencies of the calls
 std::unordered_map<const BinaryFunction *, Predecessors>
 extractFunctionCalls(const std::vector<BinaryFunction *> &BinaryFunctions) {
   std::unordered_map<const BinaryFunction *, Predecessors> Calls;
 
   for (BinaryFunction *SrcFunction : BinaryFunctions) {
     const BinaryContext &BC = SrcFunction->getBinaryContext();
-    for (BinaryBasicBlock *BB : SrcFunction->layout()) {
+    for (BinaryBasicBlock *BB : SrcFunction->getLayout().blocks()) {
       // Find call instructions and extract target symbols from each one
       for (MCInst &Inst : *BB) {
         if (!BC.MIB->isCall(Inst))
           continue;
 
         // Call info
         const MCSymbol *DstSym = BC.MIB->getTargetSymbol(Inst);
         uint64_t Count = BB->getKnownExecutionCount();
         // Ignore calls w/o information
         if (DstSym == nullptr || Count == 0)
           continue;
 
         const BinaryFunction *DstFunction = BC.getFunctionForSymbol(DstSym);
         // Ignore recursive calls
-        if (DstFunction == nullptr || DstFunction->layout_empty() ||
+        if (DstFunction == nullptr || DstFunction->getLayout().block_empty() ||
             DstFunction == SrcFunction)
           continue;
 
         // Record the call
         Calls[DstFunction].emplace_back(SrcFunction, Count);
       }
     }
   }
for (BinaryFunction *BF : BinaryFunctions) {
     Samples = std::max(Samples, (double)BF->getKnownExecutionCount());
     FunctionSamples[BF] = Samples;
     TotalSamples += Samples;
   }
 
   // Compute 'hotness' of the pages
   std::unordered_map<uint64_t, double> PageSamples;
   for (BinaryFunction *BF : BinaryFunctions) {
-    if (BF->layout_empty())
+    if (BF->getLayout().block_empty())
       continue;
-    double Page = BBAddr.at(BF->layout_front()) / PageSize;
+    double Page = BBAddr.at(BF->getLayout().block_front()) / PageSize;
     PageSamples[Page] += FunctionSamples.at(BF);
   }
 
   // Computing the expected number of misses for every function
   double Misses = 0;
   for (BinaryFunction *BF : BinaryFunctions) {
     // Skip the function if it has no samples
-    if (BF->layout_empty() || FunctionSamples.at(BF) == 0.0)
+    if (BF->getLayout().block_empty() || FunctionSamples.at(BF) == 0.0)
       continue;
     double Samples = FunctionSamples.at(BF);
-    double Page = BBAddr.at(BF->layout_front()) / PageSize;
+    double Page = BBAddr.at(BF->getLayout().block_front()) / PageSize;
     // The probability that the page is not present in the cache
     double MissProb = pow(1.0 - PageSamples[Page] / TotalSamples, CacheEntries);
 
     // Processing all callers of the function
     for (std::pair<BinaryFunction *, uint64_t> Pair : Calls[BF]) {
       BinaryFunction *SrcFunction = Pair.first;
-      double SrcPage = BBAddr.at(SrcFunction->layout_front()) / PageSize;
+      double SrcPage =
+          BBAddr.at(SrcFunction->getLayout().block_front()) / PageSize;
       // Is this a 'long' or a 'short' call?
       if (Page != SrcPage) {
         // This is a miss
         Misses += MissProb * Pair.second;
       }
       Samples -= Pair.second;
     }
     assert(Samples >= 0.0 && "Function samples computed incorrectly");

bolt/lib/Passes/ExtTSPReorderAlgorithm.cpp

private:
   /// Initialize algorithm's data structures
   void initialize() {
     // Create a separate MCCodeEmitter to allow lock-free execution
     BinaryContext::IndependentCodeEmitter Emitter;
     if (!opts::NoThreads)
       Emitter = BF.getBinaryContext().createIndependentMCCodeEmitter();
 
     // Initialize CFG nodes
-    AllBlocks.reserve(BF.layout_size());
+    AllBlocks.reserve(BF.getLayout().block_size());
     size_t LayoutIndex = 0;
-    for (BinaryBasicBlock *BB : BF.layout()) {
+    for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
       BB->setLayoutIndex(LayoutIndex++);
       uint64_t Size =
           std::max<uint64_t>(BB->estimateSize(Emitter.MCE.get()), 1);
       AllBlocks.emplace_back(BB, Size);
     }
 
     // Initialize edges for the blocks and compute their total in/out weights
     size_t NumEdges = 0;
for (Block &Block : AllBlocks) {
       size_t Index = Block.Index;
       Block.ExecutionCount = std::max(Block.ExecutionCount, Block.InWeight);
       Block.ExecutionCount = std::max(Block.ExecutionCount, Block.OutWeight);
       if (Index == 0 && Block.ExecutionCount == 0)
         Block.ExecutionCount = 1;
     }
 
     // Initialize chains
-    AllChains.reserve(BF.layout_size());
-    HotChains.reserve(BF.layout_size());
+    AllChains.reserve(BF.getLayout().block_size());
+    HotChains.reserve(BF.getLayout().block_size());
     for (Block &Block : AllBlocks) {
       AllChains.emplace_back(Block.Index, &Block);
       Block.CurChain = &AllChains.back();
       if (Block.ExecutionCount > 0)
         HotChains.push_back(&AllChains.back());
     }
 
     // Initialize edges
while (HotChains.size() > 1) {
                   BestGain.mergeType());
     }
   }
 
   /// Merge remaining blocks into chains w/o taking jump counts into
   /// consideration. This allows to maintain the original block order in the
   /// absense of profile data
   void mergeColdChains() {
-    for (BinaryBasicBlock *SrcBB : BF.layout()) {
+    for (BinaryBasicBlock *SrcBB : BF.getLayout().blocks()) {
       // Iterating in reverse order to make sure original fallthrough jumps are
       // merged first; this might be beneficial for code size.
       for (auto Itr = SrcBB->succ_rbegin(); Itr != SrcBB->succ_rend(); ++Itr) {
         BinaryBasicBlock *DstBB = *Itr;
         size_t SrcIndex = SrcBB->getLayoutIndex();
         size_t DstIndex = DstBB->getLayoutIndex();
         Chain *SrcChain = AllBlocks[SrcIndex].CurChain;
         Chain *DstChain = AllBlocks[DstIndex].CurChain;
llvm::stable_sort(SortedChains, [](const Chain *C1, const Chain *C2) {
       if (D1 != D2)
         return D1 > D2;
 
       // Making the order deterministic
       return C1->id() < C2->id();
     });
 
     // Collect the basic blocks in the order specified by their chains
-    Order.reserve(BF.layout_size());
+    Order.reserve(BF.getLayout().block_size());
     for (Chain *Chain : SortedChains)
       for (Block *Block : Chain->blocks())
         Order.push_back(Block->BB);
   }
 
 private:
   // The binary function
   const BinaryFunction &BF;
 
   // All CFG nodes (basic blocks)
   std::vector<Block> AllBlocks;
 
   // All chains of blocks
   std::vector<Chain> AllChains;
 
   // Active chains. The vector gets updated at runtime when chains are merged
   std::vector<Chain *> HotChains;
 
   // All edges between chains
   std::vector<Edge> AllEdges;
 };
 
 void ExtTSPReorderAlgorithm::reorderBasicBlocks(const BinaryFunction &BF,
                                                 BasicBlockOrder &Order) const {
-  if (BF.layout_empty())
+  if (BF.getLayout().block_empty())
     return;
 
   // Do not change layout of functions w/o profile information
-  if (!BF.hasValidProfile() || BF.layout_size() <= 2) {
-    for (BinaryBasicBlock *BB : BF.layout())
+  if (!BF.hasValidProfile() || BF.getLayout().block_size() <= 2) {
+    for (BinaryBasicBlock *BB : BF.getLayout().blocks())
       Order.push_back(BB);
     return;
   }
 
   // Apply the algorithm
   ExtTSP(BF).run(Order);
 
   // Verify correctness
   assert(Order[0]->isEntryPoint() && "Original entry point is not preserved");
-  assert(Order.size() == BF.layout_size() && "Wrong size of reordered layout");
+  assert(Order.size() == BF.getLayout().block_size() &&
+         "Wrong size of reordered layout");
 }
 
 } // namespace bolt
 } // namespace llvm

bolt/lib/Passes/FrameAnalysis.cpp

bool FrameAnalysis::computeArgsAccessed(BinaryFunction &BF) {
   }
 
   LLVM_DEBUG(dbgs() << "Now computing args accessed for: " << BF.getPrintName()
                     << "\n");
   bool UpdatedArgsTouched = false;
   bool NoInfo = false;
   FrameAccessAnalysis FAA(BF, getSPT(BF));
 
-  for (BinaryBasicBlock *BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     FAA.enterNewBB();
 
     for (MCInst &Inst : *BB) {
       if (!FAA.doNext(*BB, Inst) || FAA.doesEscapeStackAddress()) {
         ArgsTouchedMap[&BF].emplace(std::make_pair(-1, 0));
         NoInfo = true;
         break;
       }
bool FrameAnalysis::computeArgsAccessed(BinaryFunction &BF) {
   return UpdatedArgsTouched;
 }
 
 bool FrameAnalysis::restoreFrameIndex(BinaryFunction &BF) {
   FrameAccessAnalysis FAA(BF, getSPT(BF));
 
   LLVM_DEBUG(dbgs() << "Restoring frame indices for \"" << BF.getPrintName()
                     << "\"\n");
-  for (BinaryBasicBlock *BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     LLVM_DEBUG(dbgs() << "\tNow at BB " << BB->getName() << "\n");
     FAA.enterNewBB();
 
     for (MCInst &Inst : *BB) {
       if (!FAA.doNext(*BB, Inst))
         return false;
       LLVM_DEBUG({
         dbgs() << "\t\tNow at ";

bolt/lib/Passes/IdenticalCodeFolding.cpp

bool isIdenticalWith(const BinaryFunction &A, const BinaryFunction &B,
                      bool CongruentSymbols) {
   assert(A.hasCFG() && B.hasCFG() && "both functions should have CFG");
 
   // Compare the two functions, one basic block at a time.
   // Currently we require two identical basic blocks to have identical
   // instruction sequences and the same index in their corresponding
   // functions. The latter is important for CFG equality.
 
-  if (A.layout_size() != B.layout_size())
+  if (A.getLayout().block_size() != B.getLayout().block_size())
     return false;
 
   // Comparing multi-entry functions could be non-trivial.
   if (A.isMultiEntry() || B.isMultiEntry())
     return false;
 
   // Process both functions in either DFS or existing order.
-  const BinaryFunction::BasicBlockOrderType &OrderA =
-      opts::UseDFS ? A.dfs() : A.getLayout();
-  const BinaryFunction::BasicBlockOrderType &OrderB =
-      opts::UseDFS ? B.dfs() : B.getLayout();
+  const BinaryFunction::BasicBlockOrderType OrderA =
+      opts::UseDFS
+          ? A.dfs()
+          : BinaryFunction::BasicBlockOrderType(A.getLayout().block_begin(),
+                                                A.getLayout().block_end());
+  const BinaryFunction::BasicBlockOrderType OrderB =
+      opts::UseDFS
+          ? B.dfs()
+          : BinaryFunction::BasicBlockOrderType(B.getLayout().block_begin(),
+                                                B.getLayout().block_end());
 
   const BinaryContext &BC = A.getBinaryContext();
 
   auto BBI = OrderB.begin();
   for (const BinaryBasicBlock *BB : OrderA) {
     const BinaryBasicBlock *OtherBB = *BBI;
 
     if (BB->getLayoutIndex() != OtherBB->getLayoutIndex())
void IdenticalCodeFolding::runOnFunctions(BinaryContext &BC) {
   CongruentBucketsMap CongruentBuckets;
 
   // Hash all the functions
   auto hashFunctions = [&]() {
     NamedRegionTimer HashFunctionsTimer("hashing", "hashing", "ICF breakdown",
                                         "ICF breakdown", opts::TimeICF);
     ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {
       // Make sure indices are in-order.
-      BF.updateLayoutIndices();
+      BF.getLayout().updateLayoutIndices();
 
       // Pre-compute hash before pushing into hashtable.
       // Hash instruction operands to minimize hash collisions.
       BF.computeHash(opts::UseDFS, [&BC](const MCOperand &Op) {
         return hashInstOperand(BC, Op);
       });
     };
 

bolt/lib/Passes/IndirectCallPromotion.cpp

if (opts::ICPTopCallsites == 0) {
     // Find all the indirect callsites.
     for (auto &BFIt : BFs) {
       BinaryFunction &Function = BFIt.second;
 
       if (!Function.isSimple() || Function.isIgnored() ||
           !Function.hasProfile())
         continue;
 
-      const bool HasLayout = !Function.layout_empty();
+      const bool HasLayout = !Function.getLayout().block_empty();
 
       for (BinaryBasicBlock &BB : Function) {
         if (HasLayout && Function.isSplit() && BB.isCold())
           continue;
 
         for (MCInst &Inst : BB) {
           const bool IsJumpTable = Function.getJumpTable(Inst);
           const bool HasIndirectCallProfile =
void IndirectCallPromotion::runOnFunctions(BinaryContext &BC) {
   }
 
   for (BinaryFunction *FuncPtr : Functions) {
     BinaryFunction &Function = *FuncPtr;
 
     if (!Function.isSimple() || Function.isIgnored() || !Function.hasProfile())
       continue;
 
-    const bool HasLayout = !Function.layout_empty();
+    const bool HasLayout = !Function.getLayout().block_empty();
 
     // Total number of indirect calls issued from the current Function.
     // (a fraction of TotalIndirectCalls)
     uint64_t FuncTotalIndirectCalls = 0;
     uint64_t FuncTotalIndirectJmps = 0;
 
     std::vector<BinaryBasicBlock *> BBs;
     for (BinaryBasicBlock &BB : Function) {

bolt/lib/Passes/Inliner.cpp

Inliner::inlineCall(BinaryBasicBlock &CallerBB,
   if (Callee.size() == 1)
     return std::make_pair(FirstInlinedBB, InsertII);
 
   return std::make_pair(FirstInlinedBB, FirstInlinedBB->end());
 }
 
 bool Inliner::inlineCallsInFunction(BinaryFunction &Function) {
   BinaryContext &BC = Function.getBinaryContext();
-  std::vector<BinaryBasicBlock *> Blocks(Function.layout().begin(),
-                                         Function.layout().end());
+  std::vector<BinaryBasicBlock *> Blocks(Function.getLayout().block_begin(),
+                                         Function.getLayout().block_end());
   llvm::sort(
       Blocks, [](const BinaryBasicBlock *BB1, const BinaryBasicBlock *BB2) {
         return BB1->getKnownExecutionCount() > BB2->getKnownExecutionCount();
       });
 
   bool DidInlining = false;
   for (BinaryBasicBlock *BB : Blocks) {
     for (auto InstIt = BB->begin(); InstIt != BB->end();) {

bolt/lib/Passes/Instrumentation.cpp

void Instrumentation::instrumentFunction(BinaryFunction &Function,
   // spanning tree can be instrumentation-free since their count can be
   // inferred by solving flow equations on a bottom-up traversal of the tree.
   // Exit basic blocks are always instrumented so we start the traversal with
   // a minimum number of defined variables to make the equation solvable.
   std::stack<std::pair<const BinaryBasicBlock *, BinaryBasicBlock *>> Stack;
   std::unordered_map<const BinaryBasicBlock *,
                      std::set<const BinaryBasicBlock *>>
       STOutSet;
-  for (auto BBI = Function.layout_rbegin(); BBI != Function.layout_rend();
-       ++BBI) {
+  for (auto BBI = Function.getLayout().block_rbegin();
+       BBI != Function.getLayout().block_rend(); ++BBI) {
     if ((*BBI)->isEntryPoint() || (*BBI)->isLandingPad()) {
       Stack.push(std::make_pair(nullptr, *BBI));
       if (opts::InstrumentCalls && (*BBI)->isEntryPoint()) {
         EntryNode E;
         E.Node = BBToID[&**BBI];
         E.Address = (*BBI)->getInputOffset();
         FuncDesc->EntryNodes.emplace_back(E);
         createIndCallTargetDescription(Function, (*BBI)->getInputOffset());

bolt/lib/Passes/LongJmp.cpp

void relaxStubToLongJmp(BinaryBasicBlock &StubBB, const MCSymbol *Tgt) {
   StubBB.addInstructions(Seq.begin(), Seq.end());
 }
 
 BinaryBasicBlock *getBBAtHotColdSplitPoint(BinaryFunction &Func) {
   if (!Func.isSplit() || Func.empty())
     return nullptr;
 
   assert(!(*Func.begin()).isCold() && "Entry cannot be cold");
-  for (auto I = Func.layout_begin(), E = Func.layout_end(); I != E; ++I) {
+  for (auto I = Func.getLayout().block_begin(),
+            E = Func.getLayout().block_end();
+       I != E; ++I) {
     auto Next = std::next(I);
     if (Next != E && (*Next)->isCold())
       return *I;
   }
   llvm_unreachable("No hot-colt split point found");
 }
 
 bool shouldInsertStub(const BinaryContext &BC, const MCInst &Inst) {
void LongJmpPass::updateStubGroups() {
   update(ColdStubGroups);
 }
 
 void LongJmpPass::tentativeBBLayout(const BinaryFunction &Func) {
   const BinaryContext &BC = Func.getBinaryContext();
   uint64_t HotDot = HotAddresses[&Func];
   uint64_t ColdDot = ColdAddresses[&Func];
   bool Cold = false;
-  for (BinaryBasicBlock *BB : Func.layout()) {
+  for (const BinaryBasicBlock *BB : Func.getLayout().blocks()) {
     if (Cold || BB->isCold()) {
       Cold = true;
       BBAddresses[BB] = ColdDot;
       ColdDot += BC.computeCodeSize(BB->begin(), BB->end());
     } else {
       BBAddresses[BB] = HotDot;
       HotDot += BC.computeCodeSize(BB->begin(), BB->end());
     }

bolt/lib/Passes/LoopInversionPass.cpp

static cl::opt<bool> LoopReorder(
     cl::init(true), cl::cat(BoltCategory), cl::ReallyHidden);
 } // namespace opts
 
 namespace llvm {
 namespace bolt {
 
 bool LoopInversionPass::runOnFunction(BinaryFunction &BF) {
   bool IsChanged = false;
-  if (BF.layout_size() < 3 || !BF.hasValidProfile())
+  if (BF.getLayout().block_size() < 3 || !BF.hasValidProfile())
     return false;
 
-  BF.updateLayoutIndices();
-  for (BinaryBasicBlock *BB : BF.layout()) {
+  BF.getLayout().updateLayoutIndices();
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     if (BB->succ_size() != 1 || BB->pred_size() != 1)
       continue;
 
     BinaryBasicBlock *SuccBB = *BB->succ_begin();
     BinaryBasicBlock *PredBB = *BB->pred_begin();
     const unsigned BBIndex = BB->getLayoutIndex();
     const unsigned SuccBBIndex = SuccBB->getLayoutIndex();
     if (SuccBB == PredBB && BB != SuccBB && BBIndex != 0 && SuccBBIndex != 0 &&
if (SuccBB == PredBB && BB != SuccBB && BBIndex != 0 && SuccBBIndex != 0 &&
 
       IsChanged = true;
       BB->setLayoutIndex(SuccBBIndex);
       SuccBB->setLayoutIndex(BBIndex);
     }
   }
 
   if (IsChanged) {
-    BinaryFunction::BasicBlockOrderType NewOrder = BF.getLayout();
+    BinaryFunction::BasicBlockOrderType NewOrder(BF.getLayout().block_begin(),
+                                                 BF.getLayout().block_end());
     llvm::sort(NewOrder, [&](BinaryBasicBlock *BB1, BinaryBasicBlock *BB2) {
       return BB1->getLayoutIndex() < BB2->getLayoutIndex();
     });
-    BF.updateBasicBlockLayout(NewOrder);
+    BF.getLayout().update(NewOrder);
   }
 
   return IsChanged;
 }
 
 void LoopInversionPass::runOnFunctions(BinaryContext &BC) {
   std::atomic<uint64_t> ModifiedFuncCount{0};
   if (opts::ReorderBlocks == ReorderBasicBlocks::LT_NONE ||

bolt/lib/Passes/ReorderAlgorithm.cpp

void GreedyClusterAlgorithm::clusterBasicBlocks(const BinaryFunction &BF,
   // convert the hottest branches into fall-throughs.
 
   // This is the queue of edges from which we will pop edges and use them to
   // cluster basic blocks in a greedy fashion.
   std::vector<EdgeTy> Queue;
 
   // Initialize inter-cluster weights.
   if (ComputeEdges)
-    ClusterEdges.resize(BF.layout_size());
+    ClusterEdges.resize(BF.getLayout().block_size());
 
   // Initialize clusters and edge queue.
-  for (BinaryBasicBlock *BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     // Create a cluster for this BB.
     uint32_t I = Clusters.size();
     Clusters.emplace_back();
     std::vector<BinaryBasicBlock *> &Cluster = Clusters.back();
     Cluster.push_back(BB);
     BBToClusterMap[BB] = I;
     // Populate priority queue with edges.
     auto BI = BB->branch_info_begin();
while (!Queue.empty()) {
     Queue.pop_back();
 
     const BinaryBasicBlock *SrcBB = E.Src;
     const BinaryBasicBlock *DstBB = E.Dst;
 
     LLVM_DEBUG(dbgs() << "Popped edge "; E.print(dbgs()); dbgs() << "\n");
 
     // Case 1: BBSrc and BBDst are the same. Ignore this edge
-    if (SrcBB == DstBB || DstBB == *BF.layout_begin()) {
+    if (SrcBB == DstBB || DstBB == *BF.getLayout().block_begin()) {
       LLVM_DEBUG(dbgs() << "\tIgnored (same src, dst)\n");
       continue;
     }
 
     int I = BBToClusterMap[SrcBB];
     int J = BBToClusterMap[DstBB];
 
     // Case 2: If they are already allocated at the same cluster, just increase
int64_t MinBranchGreedyClusterAlgorithm::calculateWeight(
   auto BI = SrcBB->branch_info_begin();
   for (const BinaryBasicBlock *SuccBB : SrcBB->successors()) {
     assert(BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE &&
            "attempted reordering blocks of function with no profile data");
     assert(BI->Count <= std::numeric_limits<int64_t>::max() &&
            "overflow detected");
     // Ignore edges with same source and destination, edges that target the
     // entry block as well as the edge E itself.
-    if (SuccBB != SrcBB && SuccBB != *BF.layout_begin() && SuccBB != DstBB)
+    if (SuccBB != SrcBB && SuccBB != *BF.getLayout().block_begin() &&
+        SuccBB != DstBB)
       W -= (int64_t)BI->Count;
     ++BI;
   }
 
   // Adjust the weight by taking into account other edges with the same
   // destination.
   for (const BinaryBasicBlock *PredBB : DstBB->predecessors()) {
     // Ignore edges with same source and destination as well as the edge E
void MinBranchGreedyClusterAlgorithm::adjustQueue(std::vector<EdgeTy> &Queue,
   // source and destination in the same cluster.
   std::vector<EdgeTy> NewQueue;
   for (const EdgeTy &E : Queue) {
     const BinaryBasicBlock *SrcBB = E.Src;
     const BinaryBasicBlock *DstBB = E.Dst;
 
     // Case 1: SrcBB and DstBB are the same or DstBB is the entry block. Ignore
     // this edge.
-    if (SrcBB == DstBB || DstBB == *BF.layout_begin()) {
+    if (SrcBB == DstBB || DstBB == *BF.getLayout().block_begin()) {
       LLVM_DEBUG(dbgs() << "\tAdjustment: Ignored edge "; E.print(dbgs());
                  dbgs() << " (same src, dst)\n");
       continue;
     }
 
     int I = BBToClusterMap[SrcBB];
     int J = BBToClusterMap[DstBB];
     std::vector<BinaryBasicBlock *> &ClusterA = Clusters[I];
void MinBranchGreedyClusterAlgorithm::reset() {
   Weight.clear();
 }
 
 void TSPReorderAlgorithm::reorderBasicBlocks(const BinaryFunction &BF,
                                              BasicBlockOrder &Order) const {
   std::vector<std::vector<uint64_t>> Weight;
   std::vector<BinaryBasicBlock *> IndexToBB;
 
-  const size_t N = BF.layout_size();
+  const size_t N = BF.getLayout().block_size();
   assert(N <= std::numeric_limits<uint64_t>::digits &&
          "cannot use TSP solution for sizes larger than bits in uint64_t");
 
   // Populating weight map and index map
-  for (BinaryBasicBlock *BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     BB->setLayoutIndex(IndexToBB.size());
     IndexToBB.push_back(BB);
   }
   Weight.resize(N);
-  for (BinaryBasicBlock *BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     auto BI = BB->branch_info_begin();
     Weight[BB->getLayoutIndex()].resize(N);
     for (BinaryBasicBlock *SuccBB : BB->successors()) {
       if (BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE)
         Weight[BB->getLayoutIndex()][SuccBB->getLayoutIndex()] = BI->Count;
       ++BI;
     }
   }
while (Set != 0) {
     Visited[Last] = true;
     Order.push_back(IndexToBB[Last]);
     Set = Set & ~(1ULL << Last);
   }
   std::reverse(Order.begin(), Order.end());
 
   // Finalize layout with BBs that weren't assigned to the layout using the
   // input layout.
-  for (BinaryBasicBlock *BB : BF.layout())
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks())
     if (Visited[BB->getLayoutIndex()] == false)
       Order.push_back(BB);
 }
 
 void OptimizeReorderAlgorithm::reorderBasicBlocks(
     const BinaryFunction &BF, BasicBlockOrder &Order) const {
-  if (BF.layout_empty())
+  if (BF.getLayout().block_empty())
     return;
 
   // Cluster basic blocks.
   CAlgo->clusterBasicBlocks(BF);
 
   if (opts::PrintClusters)
     CAlgo->printClusters();
 
   // Arrange basic blocks according to clusters.
   for (ClusterAlgorithm::ClusterTy &Cluster : CAlgo->Clusters)
     Order.insert(Order.end(), Cluster.begin(), Cluster.end());
 }
 
 void OptimizeBranchReorderAlgorithm::reorderBasicBlocks(
     const BinaryFunction &BF, BasicBlockOrder &Order) const {
-  if (BF.layout_empty())
+  if (BF.getLayout().block_empty())
     return;
 
   // Cluster basic blocks.
   CAlgo->clusterBasicBlocks(BF, /* ComputeEdges = */ true);
   std::vector<ClusterAlgorithm::ClusterTy> &Clusters = CAlgo->Clusters;
   std::vector<std::unordered_map<uint32_t, uint64_t>> &ClusterEdges =
       CAlgo->ClusterEdges;
 
void OptimizeBranchReorderAlgorithm::reorderBasicBlocks(
   for (uint32_t ClusterIndex : ClusterOrder) {
     ClusterAlgorithm::ClusterTy &Cluster = Clusters[ClusterIndex];
     Order.insert(Order.end(), Cluster.begin(), Cluster.end());
   }
 }
 
 void OptimizeCacheReorderAlgorithm::reorderBasicBlocks(
     const BinaryFunction &BF, BasicBlockOrder &Order) const {
-  if (BF.layout_empty())
+  if (BF.getLayout().block_empty())
     return;
 
   const uint64_t ColdThreshold =
-      opts::ColdThreshold * (*BF.layout_begin())->getExecutionCount() / 1000;
+      opts::ColdThreshold *
+      (*BF.getLayout().block_begin())->getExecutionCount() / 1000;
 
   // Cluster basic blocks.
   CAlgo->clusterBasicBlocks(BF);
   std::vector<ClusterAlgorithm::ClusterTy> &Clusters = CAlgo->Clusters;
 
   // Compute clusters' average frequencies.
   CAlgo->computeClusterAverageFrequency(BF.getBinaryContext());
   std::vector<double> &AvgFreq = CAlgo->AvgFreq;
for (uint32_t ClusterIndex : ClusterOrder) {
     if (AvgFreq[ClusterIndex] < static_cast<double>(ColdThreshold))
       for (BinaryBasicBlock *BBPtr : Cluster)
         BBPtr->setExecutionCount(0);
   }
 }
 
 void ReverseReorderAlgorithm::reorderBasicBlocks(const BinaryFunction &BF,
                                                  BasicBlockOrder &Order) const {
-  if (BF.layout_empty())
+  if (BF.getLayout().block_empty())
     return;
 
-  BinaryBasicBlock *FirstBB = *BF.layout_begin();
+  BinaryBasicBlock *FirstBB = *BF.getLayout().block_begin();
   Order.push_back(FirstBB);
-  for (auto RLI = BF.layout_rbegin(); *RLI != FirstBB; ++RLI)
+  for (auto RLI = BF.getLayout().block_rbegin(); *RLI != FirstBB; ++RLI)
     Order.push_back(*RLI);
 }
 
 void RandomClusterReorderAlgorithm::reorderBasicBlocks(
     const BinaryFunction &BF, BasicBlockOrder &Order) const {
-  if (BF.layout_empty())
+  if (BF.getLayout().block_empty())
     return;
 
   // Cluster basic blocks.
   CAlgo->clusterBasicBlocks(BF);
   std::vector<ClusterAlgorithm::ClusterTy> &Clusters = CAlgo->Clusters;
 
   if (opts::PrintClusters)
     CAlgo->printClusters();

bolt/lib/Passes/ShrinkWrapping.cpp

if (Reg == BC.MIB->getStackPointer() || Reg == BC.MIB->getFramePointer()) {
       BC.MIB->addAnnotation(*Inst, getSlotTag(), Offset, AllocatorId);
       LLVM_DEBUG(dbgs() << "Recording CFI " << Offset << "\n");
     } else {
       IsSimple = false;
       return;
     }
   };
 
-  for (BinaryBasicBlock *&BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     for (MCInst &Inst : *BB) {
       if (!BC.MIB->isCFI(Inst))
         continue;
       const MCCFIInstruction *CFI = BF.getCFIFor(Inst);
       switch (CFI->getOperation()) {
       case MCCFIInstruction::OpDefCfa:
         CfaOffset = -CFI->getOffset();
         recordAccess(&Inst, CfaOffset);
for (ProgramPoint &PP : Frontier) {
     });
     IsCritEdge.push_back(HasCritEdges);
   }
   // Restores cannot be placed in empty BBs because we have a dataflow
   // analysis that depends on insertions happening before real instructions
   // (PredictiveStackPointerTracking). Detect now for empty BBs and add a
   // dummy nop that is scheduled to be removed later.
   bool InvalidateRequired = false;
-  for (BinaryBasicBlock *&BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     if (BB->size() != 0)
       continue;
     MCInst NewInst;
     BC.MIB->createNoop(NewInst);
     auto II = BB->addInstruction(std::move(NewInst));
     scheduleChange(&*II, WorklistItem(WorklistItem::Erase, 0));
     InvalidateRequired = true;
   }
for (ProgramPoint &PP : FixedRestorePoints) {
     }
   }
   return FixedRestorePoints;
 }
 
 void ShrinkWrapping::scheduleOldSaveRestoresRemoval(unsigned CSR,
                                                     bool UsePushPops) {
 
-  for (BinaryBasicBlock *&BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     std::vector<MCInst *> CFIs;
     for (auto I = BB->rbegin(), E = BB->rend(); I != E; ++I) {
       MCInst &Inst = *I;
       if (BC.MIB->isCFI(Inst)) {
         // Delete all offset CFIs related to this CSR
         if (SLM.getOffsetCFIReg(Inst) == CSR) {
           HasDeletedOffsetCFIs[CSR] = true;
           scheduleChange(&Inst, WorklistItem(WorklistItem::Erase, CSR));
void ShrinkWrapping::insertUpdatedCFI(unsigned CSR, int SPValPush,
   assert(SavePoint);
   LLVM_DEBUG({
     dbgs() << "Now using as save point for reg " << CSR << " :";
     SavePoint->dump();
   });
   bool PrevAffectedZone = false;
   BinaryBasicBlock *PrevBB = nullptr;
   DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();
-  for (BinaryBasicBlock *BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     if (BB->size() == 0)
       continue;
     const bool InAffectedZoneAtEnd = DA.count(*BB->rbegin(), *SavePoint);
     const bool InAffectedZoneAtBegin =
         (*DA.getStateBefore(*BB->begin()))[DA.ExprToIdx[SavePoint]];
     bool InAffectedZone = InAffectedZoneAtBegin;
     for (auto InstIter = BB->begin(); InstIter != BB->end(); ++InstIter) {
       const bool CurZone = DA.count(*InstIter, *SavePoint);
for (MCInst &Inst : BB) {
       if (CFI->getOperation() == MCCFIInstruction::OpDefCfaOffset)
         BC.MIB->addAnnotation(Inst, "DeleteMe", 0U, AllocatorId);
     }
   }
 
   int PrevSPVal = -8;
   BinaryBasicBlock *PrevBB = nullptr;
   StackPointerTracking &SPT = Info.getStackPointerTracking();
-  for (BinaryBasicBlock *BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     if (BB->size() == 0)
       continue;
     const int SPValAtEnd = SPT.getStateAt(*BB->rbegin())->first;
     const int SPValAtBegin = SPT.getStateBefore(*BB->begin())->first;
     int SPVal = SPValAtBegin;
     for (auto Iter = BB->begin(); Iter != BB->end(); ++Iter) {
       const int CurVal = SPT.getStateAt(*Iter)->first;
       if (SPVal != CurVal) {

 bool ShrinkWrapping::perform(bool HotOnly) {
   HasDeletedOffsetCFIs = BitVector(BC.MRI->getNumRegs(), false);
   PushOffsetByReg = std::vector<int64_t>(BC.MRI->getNumRegs(), 0LL);
   PopOffsetByReg = std::vector<int64_t>(BC.MRI->getNumRegs(), 0LL);
 
   // Update pass statistics
   uint64_t TotalInstrs = 0ULL;
   uint64_t TotalStoreInstrs = 0ULL;
-  for (BinaryBasicBlock *BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     uint64_t BBExecCount = BB->getExecutionCount();
     if (!BBExecCount || BBExecCount == BinaryBasicBlock::COUNT_NO_PROFILE)
       continue;
     for (const auto &Instr : *BB) {
       if (BC.MIB->isPseudo(Instr))
         continue;
       if (BC.MIB->isStore(Instr))
         TotalStoreInstrs += BBExecCount;

bolt/lib/Passes/SplitFunctions.cpp

bool canSplit(const BinaryFunction &BF) {
 
     return !AllCold;
   }
 
   bool canOutline(const BinaryBasicBlock &BB) {
     return BB.getExecutionCount() == 0;
   }
 
-  void partition(BinaryFunction::reverse_order_iterator Start,
-                 BinaryFunction::reverse_order_iterator End) const {
+  template <typename It> void partition(const It Start, const It End) const {
     for (auto I = Start; I != End; ++I) {
       BinaryBasicBlock *BB = *I;
       if (!BB->canOutline())
         break;
       BB->setIsCold(true);
     }
   }
 };
 
 struct SplitRandom {
   std::minstd_rand0 *Gen;
 
   explicit SplitRandom(std::minstd_rand0 &Gen) : Gen(&Gen) {}
 
   bool canSplit(const BinaryFunction &BF) { return true; }
   bool canOutline(const BinaryBasicBlock &BB) { return true; }
 
-  void partition(BinaryFunction::reverse_order_iterator Start,
-                 BinaryFunction::reverse_order_iterator End) const {
-    using It = decltype(Start);
+  template <typename It> void partition(It Start, It End) const {
+    using DiffT = typename It::difference_type;
 
     const It OutlineableBegin = Start;
     const It OutlineableEnd =
-        std::find_if(OutlineableBegin, End,
-                     [](BinaryBasicBlock *BB) { return !BB->canOutline(); });
-    const It::difference_type NumOutlineableBlocks =
-        OutlineableEnd - OutlineableBegin;
+        std::find_if(OutlineableBegin, End, [](const BinaryBasicBlock *BB) {
+          return !BB->canOutline();
+        });
+    const DiffT NumOutlineableBlocks = OutlineableEnd - OutlineableBegin;
 
     // We want to split at least one block unless there are not blocks that can
     // be outlined
-    const auto MinimumSplit =
-        std::min<It::difference_type>(NumOutlineableBlocks, 1);
-    std::uniform_int_distribution<It::difference_type> Dist(
-        MinimumSplit, NumOutlineableBlocks);
-    const It::difference_type NumColdBlocks = Dist(*Gen);
+    const auto MinimumSplit = std::min<DiffT>(NumOutlineableBlocks, 1);
+    std::uniform_int_distribution<DiffT> Dist(MinimumSplit,
+                                              NumOutlineableBlocks);
+    const DiffT NumColdBlocks = Dist(*Gen);
     const It ColdEnd = OutlineableBegin + NumColdBlocks;
 
     LLVM_DEBUG(dbgs() << formatv("BOLT-DEBUG: randomly chose last {0} (out of "
                                  "{1} possible) blocks to split\n",
                                  ColdEnd - OutlineableBegin,
                                  OutlineableEnd - OutlineableBegin));
 
     std::for_each(OutlineableBegin, ColdEnd,

 template <typename SplitStrategy>
 void SplitFunctions::splitFunction(BinaryFunction &BF, SplitStrategy Strategy) {
   if (BF.empty())
     return;
 
   if (!Strategy.canSplit(BF))
     return;
 
-  BinaryFunction::BasicBlockOrderType PreSplitLayout = BF.getLayout();
+  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;
   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");
   }
 
+  BinaryFunction::BasicBlockOrderType NewLayout(Layout.block_begin(),
+                                                Layout.block_end());
   // Never outline the first basic block.
-  BF.layout_front()->setCanOutline(false);
-  for (BinaryBasicBlock *BB : BF.layout()) {
+  NewLayout.front()->setCanOutline(false);
+  for (BinaryBasicBlock *const BB : NewLayout) {
     if (!BB->canOutline())
       continue;
     if (!Strategy.canOutline(*BB)) {
       BB->setCanOutline(false);
       continue;
     }
     // Do not split extra entry points in aarch64. They can be referred by
     // using ADRs and when this happens, these blocks cannot be placed far
if (BF.hasEHRanges() && !opts::SplitEH) {
       }
     }
   }
 
   if (opts::AggressiveSplitting) {
     // All blocks with 0 count that we can move go to the end of the function.
     // Even if they were natural to cluster formation and were seen in-between
     // hot basic blocks.
-    llvm::stable_sort(BF.layout(),
-                      [&](BinaryBasicBlock *A, BinaryBasicBlock *B) {
-                        return A->canOutline() < B->canOutline();
-                      });
+    stable_sort(NewLayout, [&](BinaryBasicBlock *A, BinaryBasicBlock *B) {
   } else if (BF.hasEHRanges() && !opts::SplitEH) {
     // Typically functions with exception handling have landing pads at the end.
     // We cannot move beginning of landing pads, but we can move 0-count blocks
     // comprising landing pads to the end and thus facilitate splitting.
-    auto FirstLP = BF.layout_begin();
+    auto FirstLP = NewLayout.begin();
     while ((*FirstLP)->isLandingPad())
       ++FirstLP;
 
-    std::stable_sort(FirstLP, BF.layout_end(),
+    std::stable_sort(FirstLP, NewLayout.end(),
                      [&](BinaryBasicBlock *A, BinaryBasicBlock *B) {
                        return A->canOutline() < B->canOutline();
                      });
   }
 
   // Separate hot from cold starting from the bottom.
-  Strategy.partition(BF.layout_rbegin(), BF.layout_rend());
+  Strategy.partition(NewLayout.rbegin(), NewLayout.rend());
+  BF.getLayout().update(NewLayout);
 
   // For shared objects, invoke instructions and corresponding landing pads
   // 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);
 
if (alignTo(OriginalHotSize, opts::SplitAlignThreshold) <=
                         << Twine::utohexstr(OriginalHotSize) << '\n');
 
       // 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);
 
-      BF.updateBasicBlockLayout(PreSplitLayout);
       for (BinaryBasicBlock &BB : BF)
         BB.setIsCold(false);
+      BF.getLayout().update(PreSplitLayout);
     } else {
       SplitBytesHot += HotSize;
       SplitBytesCold += ColdSize;
     }
   }
 }
 
 SplitFunctions::TrampolineSetType
for (BinaryBasicBlock *BB : Blocks) {
     }
   }
 
   if (LPTrampolines.empty())
     return LPTrampolines;
 
   // All trampoline blocks were added to the end of the function. Place them at
   // the end of corresponding fragments.
-  std::stable_sort(BF.layout_begin(), BF.layout_end(),
-                   [&](BinaryBasicBlock *A, BinaryBasicBlock *B) {
-                     return A->isCold() < B->isCold();
-                   });
+  BinaryFunction::BasicBlockOrderType NewLayout(BF.getLayout().block_begin(),
+                                                BF.getLayout().block_end());
+  stable_sort(NewLayout, [&](BinaryBasicBlock *A, BinaryBasicBlock *B) {
+  BF.getLayout().update(NewLayout);
 
   // Conservatively introduce branch instructions.
   BF.fixBranches();
 
   // Update exception-handling CFG for the function.
   BF.recomputeLandingPads();
 
   return LPTrampolines;

bolt/lib/Passes/StokeInfo.cpp

if (NameVec)
       NameVec->insert(std::string(BC.MRI->getName(RegIdx)));
   }
   LLVM_DEBUG(dbgs() << "\n");
 }
 
 void StokeInfo::checkInstr(const BinaryFunction &BF, StokeFuncInfo &FuncInfo) {
   MCPlusBuilder *MIB = BF.getBinaryContext().MIB.get();
   BitVector RegV(NumRegs, false);
-  for (BinaryBasicBlock *BB : BF.layout()) {
+  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     if (BB->empty())
       continue;
 
     for (MCInst &It : *BB) {
       if (MIB->isPseudo(It))
         continue;
       // skip function with exception handling yet
       if (MIB->isEHLabel(It) || MIB->isInvoke(It)) {
for (MCInst &It : *BB) {
         FuncInfo.StackOut = true;
 
       if (MIB->isStore(It) && !IsPush && !IsRipAddr)
         FuncInfo.HeapOut = true;
 
       if (IsRipAddr)
         FuncInfo.HasRipAddr = true;
     } // end of for (auto &It : ...)
-  } // end of for (auto *BB : ...)
+  }   // end of for (auto *BB : ...)
 }
 
 bool StokeInfo::checkFunction(BinaryFunction &BF, DataflowInfoManager &DInfo,
                               RegAnalysis &RA, StokeFuncInfo &FuncInfo) {
 
   std::string Name = BF.getSymbol()->getName().str();
 
   if (!BF.isSimple() || BF.isMultiEntry() || BF.empty())

bolt/lib/Passes/TailDuplication.cpp

void TailDuplication::constantAndCopyPropagate(
   }
 }
 
 bool TailDuplication::isInCacheLine(const BinaryBasicBlock &BB,
                                     const BinaryBasicBlock &Succ) const {
   if (&BB == &Succ)
     return true;
 
-  BinaryFunction::BasicBlockOrderType BlockLayout =
-      BB.getFunction()->getLayout();
   uint64_t Distance = 0;
   int Direction = (Succ.getLayoutIndex() > BB.getLayoutIndex()) ? 1 : -1;
 
   for (unsigned I = BB.getLayoutIndex() + Direction; I != Succ.getLayoutIndex();
        I += Direction) {
-    Distance += BlockLayout[I]->getOriginalSize();
+    Distance += BB.getFunction()->getLayout().getBlock(I)->getOriginalSize();
     if (Distance > opts::TailDuplicationMinimumOffset)
       return false;
   }
   return true;
 }
 
 std::vector<BinaryBasicBlock *>
 TailDuplication::moderateDuplicate(BinaryBasicBlock &BB,
return (IsForwardJump ? 1.0 : opts::TailDuplicationCacheBackwardWeight) *
          Prob * Count;
 }
 
 bool TailDuplication::cacheScoreImproved(const MCCodeEmitter *Emitter,
                                          BinaryFunction &BF,
                                          BinaryBasicBlock *Pred,
                                          BinaryBasicBlock *Tail) const {
   // Collect (estimated) basic block sizes
-  DenseMap<BinaryBasicBlock *, uint64_t> BBSize;
-  for (BinaryBasicBlock *BB : BF.layout()) {
-    BBSize[BB] = std::max<uint64_t>(BB->estimateSize(Emitter), 1);
+  DenseMap<const BinaryBasicBlock *, uint64_t> BBSize;
+  for (const BinaryBasicBlock &BB : BF) {
+    BBSize[&BB] = std::max<uint64_t>(BB.estimateSize(Emitter), 1);
   }
 
   // Build current addresses of basic blocks starting at the entry block
   DenseMap<BinaryBasicBlock *, uint64_t> CurAddr;
   uint64_t Addr = 0;
-  for (BinaryBasicBlock *SrcBB : BF.layout()) {
+  for (BinaryBasicBlock *SrcBB : BF.getLayout().blocks()) {
     CurAddr[SrcBB] = Addr;
     Addr += BBSize[SrcBB];
   }
 
   // Build new addresses (after duplication) starting at the entry block
   DenseMap<BinaryBasicBlock *, uint64_t> NewAddr;
   Addr = 0;
-  for (BinaryBasicBlock *SrcBB : BF.layout()) {
+  for (BinaryBasicBlock *SrcBB : BF.getLayout().blocks()) {
     NewAddr[SrcBB] = Addr;
     Addr += BBSize[SrcBB];
     if (SrcBB == Pred)
       Addr += BBSize[Tail];
   }
 
   // Compute the cache score for the existing layout of basic blocks
   double CurScore = 0;
-  for (BinaryBasicBlock *SrcBB : BF.layout()) {
+  for (BinaryBasicBlock *SrcBB : BF.getLayout().blocks()) {
     auto BI = SrcBB->branch_info_begin();
     for (BinaryBasicBlock *DstBB : SrcBB->successors()) {
       if (SrcBB != DstBB) {
         CurScore += cacheScore(CurAddr[SrcBB], BBSize[SrcBB], CurAddr[DstBB],
                                BBSize[DstBB], BI->Count);
       }
       ++BI;
     }
   }
 
   // Compute the cache score for the layout of blocks after tail duplication
   double NewScore = 0;
-  for (BinaryBasicBlock *SrcBB : BF.layout()) {
+  for (BinaryBasicBlock *SrcBB : BF.getLayout().blocks()) {
     auto BI = SrcBB->branch_info_begin();
     for (BinaryBasicBlock *DstBB : SrcBB->successors()) {
       if (SrcBB != DstBB) {
         if (SrcBB == Pred && DstBB == Tail) {
           NewScore += cacheScore(NewAddr[SrcBB], BBSize[SrcBB],
                                  NewAddr[SrcBB] + BBSize[SrcBB], BBSize[DstBB],
                                  BI->Count);
         } else {
if (Tail->estimateSize(Emitter) <= opts::TailDuplicationMinimumDuplication) {
     BlocksToDuplicate.push_back(Tail);
     return BlocksToDuplicate;
   }
   // Never duplicate "large" tail basic blocks
   if (Tail->estimateSize(Emitter) > opts::TailDuplicationMaximumDuplication) {
     return BlocksToDuplicate;
   }
   // Do not append basic blocks after the last hot block in the current layout
-  auto NextBlock = BF.getBasicBlockAfter(Pred);
+  auto NextBlock = BF.getLayout().getBasicBlockAfter(Pred);
   if (NextBlock == nullptr || (!Pred->isCold() && NextBlock->isCold())) {
     return BlocksToDuplicate;
   }
 
   // Duplicate the tail only if it improves the cache score
   if (cacheScoreImproved(Emitter, BF, Pred, Tail)) {
     BlocksToDuplicate.push_back(Tail);
   }

 
 void TailDuplication::runOnFunction(BinaryFunction &Function) {
   // Create a separate MCCodeEmitter to allow lock-free execution
   BinaryContext::IndependentCodeEmitter Emitter;
   if (!opts::NoThreads) {
     Emitter = Function.getBinaryContext().createIndependentMCCodeEmitter();
   }
 
-  Function.updateLayoutIndices();
+  Function.getLayout().updateLayoutIndices();
 
   // New blocks will be added and layout will change,
   // so make a copy here to iterate over the original layout
-  BinaryFunction::BasicBlockOrderType BlockLayout = Function.getLayout();
+  BinaryFunction::BasicBlockOrderType BlockLayout(
+      Function.getLayout().block_begin(), Function.getLayout().block_end());
   bool ModifiedFunction = false;
   for (BinaryBasicBlock *BB : BlockLayout) {
     AllDynamicCount += BB->getKnownExecutionCount();
 
     // The block must be with one successor
     if (BB->succ_size() != 1)
       continue;
     BinaryBasicBlock *Tail = BB->getSuccessor();
if (opts::TailDuplicationConstCopyPropagation) {
       if (FirstBB->pred_size() == 1) {
         BinaryBasicBlock *PredBB = *FirstBB->pred_begin();
         if (PredBB->succ_size() == 1)
           constantAndCopyPropagate(*PredBB, BlocksToDuplicate);
       }
     }
 
     // Layout indices might be stale after duplication
-    Function.updateLayoutIndices();
+    Function.getLayout().updateLayoutIndices();
   }
   if (ModifiedFunction)
     ModifiedFunctions++;
 }
 
 void TailDuplication::runOnFunctions(BinaryContext &BC) {
   if (opts::TailDuplicationMode == TailDuplication::TD_NONE)
     return;

bolt/lib/Passes/ThreeWayBranch.cpp

bool ThreeWayBranch::shouldRunOnFunction(BinaryFunction &Function) {
   return true;
 }
 
 void ThreeWayBranch::runOnFunction(BinaryFunction &Function) {
   BinaryContext &BC = Function.getBinaryContext();
   MCContext *Ctx = BC.Ctx.get();
   // New blocks will be added and layout will change,
   // so make a copy here to iterate over the original layout
-  BinaryFunction::BasicBlockOrderType BlockLayout = Function.getLayout();
+  BinaryFunction::BasicBlockOrderType BlockLayout(
+      Function.getLayout().block_begin(), Function.getLayout().block_end());
   for (BinaryBasicBlock *BB : BlockLayout) {
     // The block must be hot
     if (BB->getExecutionCount() == 0 ||
         BB->getExecutionCount() == BinaryBasicBlock::COUNT_NO_PROFILE)
       continue;
     // with two successors
     if (BB->succ_size() != 2)
       continue;

bolt/lib/Passes/ValidateInternalCalls.cpp

for (auto I = RI.expr_begin(Return), E = RI.expr_end(); I != E; ++I) {
 
       // Mark this call as processed, so we don't try to analyze it as a
       // PIC-computation internal call.
       BC.MIB->addAnnotation(ReachingInst, getProcessedICTag(), 0U);
 
       // Connect this block with the returning block of the caller
       BinaryBasicBlock *CallerBlock = Info.getInsnToBBMap()[&ReachingInst];
       BinaryBasicBlock *ReturnDestBlock =
-          Function.getBasicBlockAfter(CallerBlock);
+          Function.getLayout().getBasicBlockAfter(CallerBlock);
       BB.addSuccessor(ReturnDestBlock, BB.getExecutionCount(), 0);
     }
   };
 
   // This will connect blocks terminated with RETs to their respective
   // internal caller return block. A note here: this is overly conservative
   // because in nested calls, or unrelated calls, it will create edges
   // connecting RETs to potentially unrelated internal calls. This is safe

bolt/lib/Profile/BoltAddressTranslation.cpp

for (auto &BFI : BC.getBinaryFunctions()) {
     if (!BC.HasRelocations && !Function.isSimple())
       continue;
 
     LLVM_DEBUG(dbgs() << "Function name: " << Function.getPrintName() << "\n");
     LLVM_DEBUG(dbgs() << " Address reference: 0x"
                       << Twine::utohexstr(Function.getOutputAddress()) << "\n");
     MapTy Map;
     const bool IsSplit = Function.isSplit();
-    for (BinaryBasicBlock *&BB : Function.layout()) {
+    for (const BinaryBasicBlock *BB : Function.getLayout().blocks()) {
       if (IsSplit && BB->isCold())
         break;
       writeEntriesForBB(Map, *BB, Function.getOutputAddress());
     }
     Maps.insert(std::pair<uint64_t, MapTy>(Function.getOutputAddress(), Map));
 
     if (!IsSplit)
       continue;
 
     // Cold map
     Map.clear();
     LLVM_DEBUG(dbgs() << " Cold part\n");
-    for (BinaryBasicBlock *&BB : Function.layout()) {
+    for (const BinaryBasicBlock *BB : Function.getLayout().blocks()) {
       if (!BB->isCold())
         continue;
       writeEntriesForBB(Map, *BB, Function.cold().getAddress());
     }
     Maps.insert(std::pair<uint64_t, MapTy>(Function.cold().getAddress(), Map));
     ColdPartSource.insert(std::pair<uint64_t, uint64_t>(
         Function.cold().getAddress(), Function.getOutputAddress()));
   }

bolt/lib/Profile/DataAggregator.cpp

bool DataAggregator::recordTrace(
 
   if (!FromBB || !ToBB)
     return false;
 
   // Adjust FromBB if the first LBR is a return from the last instruction in
   // the previous block (that instruction should be a call).
   if (From == FromBB->getOffset() && !BF.containsAddress(FirstLBR.From) &&
       !FromBB->isEntryPoint() && !FromBB->isLandingPad()) {
-    BinaryBasicBlock *PrevBB = BF.BasicBlocksLayout[FromBB->getIndex() - 1];
+    BinaryBasicBlock *PrevBB = BF.getLayout().getBlock(FromBB->getIndex() - 1);
     if (PrevBB->getSuccessor(FromBB->getLabel())) {
       const MCInst *Instr = PrevBB->getLastNonPseudoInstr();
       if (Instr && BC.MIB->isCall(*Instr))
         FromBB = PrevBB;
       else
         LLVM_DEBUG(dbgs() << "invalid incoming LBR (no call): " << FirstLBR
                           << '\n');
     } else {
       LLVM_DEBUG(dbgs() << "invalid incoming LBR: " << FirstLBR << '\n');
     }
   }
 
   // Fill out information for fall-through edges. The From and To could be
   // within the same basic block, e.g. when two call instructions are in the
   // same block. In this case we skip the processing.
   if (FromBB == ToBB)
     return true;
 
   // Process blocks in the original layout order.
-  BinaryBasicBlock *BB = BF.BasicBlocksLayout[FromBB->getIndex()];
+  BinaryBasicBlock *BB = BF.getLayout().getBlock(FromBB->getIndex());
   assert(BB == FromBB && "index mismatch");
   while (BB != ToBB) {
-    BinaryBasicBlock *NextBB = BF.BasicBlocksLayout[BB->getIndex() + 1];
+    BinaryBasicBlock *NextBB = BF.getLayout().getBlock(BB->getIndex() + 1);
     assert((NextBB && NextBB->getOffset() > BB->getOffset()) && "bad layout");
 
     // Check for bad LBRs.
     if (!BB->getSuccessor(NextBB->getLabel())) {
       LLVM_DEBUG(dbgs() << "no fall-through for the trace:\n"
                         << "  " << FirstLBR << '\n'
                         << "  " << SecondLBR << '\n');
       return false;

bolt/lib/Profile/DataReader.cpp

if (LastInstr) {
         LLVM_DEBUG(dbgs() << "branch recorded into the middle of the block"
                           << " in " << BF << " : " << From << " -> " << To
                           << '\n');
         return false;
       }
     }
 
     // The real destination is the layout successor of the detected ToBB.
-    if (ToBB == BF.BasicBlocksLayout.back())
+    if (ToBB == BF.getLayout().block_back())
       return false;
-    BinaryBasicBlock *NextBB = BF.BasicBlocksLayout[ToBB->getIndex() + 1];
+    BinaryBasicBlock *NextBB = BF.getLayout().getBlock(ToBB->getIndex() + 1);
     assert((NextBB && NextBB->getOffset() > ToBB->getOffset()) && "bad layout");
     ToBB = NextBB;
   }
 
   // If there's no corresponding instruction for 'From', we have probably
   // discarded it as a FT from __builtin_unreachable.
   MCInst *FromInstruction = BF.getInstructionAtOffset(From);
   if (!FromInstruction) {

bolt/lib/Rewrite/BoltDiff.cpp

class RewriteInstanceDiff {
   /// For a function in binary 2 that matched one in binary 1, now match each
   /// individual basic block in it to its corresponding blocks in binary 1.
   /// Also match each edge in binary 2 to the corresponding ones in binary 1.
   void matchBasicBlocks() {
     for (const auto &MapEntry : FuncMap) {
       const BinaryFunction *const &Func1 = MapEntry.second;
       const BinaryFunction *const &Func2 = MapEntry.first;
 
-      auto Iter1 = Func1->layout_begin();
-      auto Iter2 = Func2->layout_begin();
+      auto Iter1 = Func1->getLayout().block_begin();
+      auto Iter2 = Func2->getLayout().block_begin();
 
       bool Match = true;
       std::map<const BinaryBasicBlock *, const BinaryBasicBlock *> Map;
       std::map<double, std::pair<EdgeTy, EdgeTy>> EMap;
-      while (Iter1 != Func1->layout_end()) {
-        if (Iter2 == Func2->layout_end()) {
+      while (Iter1 != Func1->getLayout().block_end()) {
+        if (Iter2 == Func2->getLayout().block_end()) {
           Match = false;
           break;
         }
         if (!compareBBs(**Iter1, **Iter2)) {
           Match = false;
           break;
         }
         Map.insert(std::make_pair<>(*Iter2, *Iter1));
for (const auto &MapEntry : FuncMap) {
         if (!Match)
           break;
 
         BBToFuncMap[*Iter1] = Func1;
         BBToFuncMap[*Iter2] = Func2;
         ++Iter1;
         ++Iter2;
       }
-      if (!Match || Iter2 != Func2->layout_end())
+      if (!Match || Iter2 != Func2->getLayout().block_end())
         continue;
 
       BBMap.insert(Map.begin(), Map.end());
       EdgeMap.insert(EMap.begin(), EMap.end());
     }
   }
 
   /// Print the largest differences in basic block performance from binary 1