diff --git a/bolt/include/bolt/Core/BinaryEmitter.h b/bolt/include/bolt/Core/BinaryEmitter.h
--- a/bolt/include/bolt/Core/BinaryEmitter.h
+++ b/bolt/include/bolt/Core/BinaryEmitter.h
@@ -35,7 +35,7 @@
 /// Emit \p BF function code. The caller is responsible for emitting function
 /// symbol(s) and setting the section to emit the code to.
 void emitFunctionBody(MCStreamer &Streamer, BinaryFunction &BF,
-                      const FunctionFragment &FF, bool EmitCodeOnly);
+                      FunctionFragment &FF, bool EmitCodeOnly);
 
 } // namespace bolt
 } // namespace llvm
diff --git a/bolt/include/bolt/Core/FunctionLayout.h b/bolt/include/bolt/Core/FunctionLayout.h
--- a/bolt/include/bolt/Core/FunctionLayout.h
+++ b/bolt/include/bolt/Core/FunctionLayout.h
@@ -25,6 +25,7 @@
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include <iterator>
+#include <utility>
 
 namespace llvm {
 namespace bolt {
@@ -70,28 +71,41 @@
   using FragmentListType = SmallVector<unsigned, 0>;
 
 public:
-  using const_iterator = BasicBlockListType::const_iterator;
+  using iterator = raw_pointer_iterator<BasicBlockListType::const_iterator,
+                                        BinaryBasicBlock>;
+  using const_iterator =
+      raw_pointer_iterator<BasicBlockListType::const_iterator,
+                           const BinaryBasicBlock>;
 
 private:
+  FunctionLayout *Layout;
   FragmentNum Num;
-  const FunctionLayout &Layout;
+  unsigned StartIndex;
+  unsigned Size = 0;
 
-  FunctionFragment(FragmentNum Num, const FunctionLayout &Layout)
-      : Num(Num), Layout(Layout) {}
+  FunctionFragment(FunctionLayout &Layout, FragmentNum Num);
+  FunctionFragment(const FunctionFragment &) = default;
+  FunctionFragment(FunctionFragment &&) = default;
+  FunctionFragment &operator=(const FunctionFragment &) = default;
+  FunctionFragment &operator=(FunctionFragment &&) = default;
+  ~FunctionFragment() = default;
 
 public:
   FragmentNum getFragmentNum() const { return Num; }
-  bool isMainFragment() const { return Num.get() == 0; }
-  bool isSplitFragment() const { return Num.get() > 0; }
+  bool isMainFragment() const {
+    return getFragmentNum() == FragmentNum::main();
+  }
+  bool isSplitFragment() const { return !isMainFragment(); }
 
-  unsigned size() const;
-  bool empty() const;
+  unsigned size() const { return Size; };
+  bool empty() const { return size() == 0; };
+  iterator begin();
   const_iterator begin() const;
+  iterator end();
   const_iterator end() const;
-  BinaryBasicBlock *front() const;
+  const BinaryBasicBlock *front() const;
 
   friend class FunctionLayout;
-  friend class FragmentIterator;
 };
 
 /// The function layout represents the fragments we split a function into and
@@ -104,92 +118,76 @@
 /// iterating either over fragments or over BinaryFunction::begin()..end().
 class FunctionLayout {
 private:
+  using FragmentListType = SmallVector<FunctionFragment *, 0>;
   using BasicBlockListType = SmallVector<BinaryBasicBlock *, 0>;
-  using block_iterator = BasicBlockListType::iterator;
-  using FragmentListType = SmallVector<unsigned, 0>;
 
 public:
-  class FragmentIterator
-      : public iterator_facade_base<
-            FragmentIterator, std::bidirectional_iterator_tag, FunctionFragment,
-            std::ptrdiff_t, FunctionFragment *, FunctionFragment> {
-    FragmentNum Num;
-    const FunctionLayout *Layout;
-
-    FragmentIterator(FragmentNum Num, const FunctionLayout *Layout)
-        : Num(Num), Layout(Layout) {
-      assert(Num.get() <= Layout->fragment_size() &&
-             "Initializing iterator out of bounds");
-    }
-
-  public:
-    bool operator==(const FragmentIterator &Other) const {
-      return Num == Other.Num;
-    }
-
-    FunctionFragment operator*() const {
-      assert(Num.get() < Layout->fragment_size() &&
-             "Dereferencing end() iterator (or past it)");
-      return FunctionFragment(Num, *Layout);
-    }
-
-    FragmentIterator &operator++() {
-      assert(Num.get() < Layout->fragment_size() &&
-             "Incrementing iterator past end()");
-      Num = FragmentNum(Num.get() + 1);
-      return *this;
-    }
-
-    FragmentIterator &operator--() {
-      assert(Num.get() > 0 && "Decrementing iterator past begin()");
-      Num = FragmentNum(Num.get() - 1);
-      return *this;
-    }
-
-    friend class FunctionLayout;
-  };
-
-  using const_iterator = FragmentIterator;
-  using block_const_iterator = BasicBlockListType::const_iterator;
+  using fragment_iterator = pointee_iterator<FragmentListType::const_iterator>;
+  using fragment_const_iterator =
+      pointee_iterator<FragmentListType::const_iterator,
+                       const FunctionFragment>;
+  using block_iterator = BasicBlockListType::iterator;
+  using block_const_iterator =
+      raw_pointer_iterator<BasicBlockListType::const_iterator,
+                           const BinaryBasicBlock>;
+  using block_reverse_iterator = std::reverse_iterator<block_iterator>;
   using block_const_reverse_iterator =
       std::reverse_iterator<block_const_iterator>;
 
 private:
+  FragmentListType Fragments;
   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`. Always contains at least one
-  /// fragment.
-  FragmentListType Fragments = {0, 0};
 
 public:
+  FunctionLayout();
+  FunctionLayout(const FunctionLayout &Other);
+  FunctionLayout(FunctionLayout &&Other);
+  FunctionLayout &operator=(const FunctionLayout &Other);
+  FunctionLayout &operator=(FunctionLayout &&Other);
+  ~FunctionLayout();
+
   /// Add an empty fragment.
-  FunctionFragment addFragment();
+  FunctionFragment &addFragment();
 
   /// Return the fragment identified by Num.
-  FunctionFragment getFragment(FragmentNum Num) const;
+  FunctionFragment &getFragment(FragmentNum Num);
+
+  /// Return the fragment identified by Num.
+  const FunctionFragment &getFragment(FragmentNum Num) const;
 
   /// Get the fragment that contains all entry blocks and other blocks that
   /// cannot be split.
-  FunctionFragment getMainFragment() const {
+  FunctionFragment &getMainFragment() {
     return getFragment(FragmentNum::main());
   }
 
   /// Get the fragment that contains all entry blocks and other blocks that
   /// cannot be split.
-  iterator_range<const_iterator> getSplitFragments() const {
+  const FunctionFragment &getMainFragment() const {
+    return getFragment(FragmentNum::main());
+  }
+
+  /// Get the fragment that contains all entry blocks and other blocks that
+  /// cannot be split.
+  iterator_range<fragment_iterator> getSplitFragments() {
+    return {++fragment_begin(), fragment_end()};
+  }
+
+  /// Get the fragment that contains all entry blocks and other blocks that
+  /// cannot be split.
+  iterator_range<fragment_const_iterator> getSplitFragments() const {
     return {++fragment_begin(), fragment_end()};
   }
 
   /// Find the fragment that contains BB.
-  FunctionFragment findFragment(const BinaryBasicBlock *BB) const;
+  const 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,
+  void insertBasicBlocks(const BinaryBasicBlock *InsertAfter,
                          ArrayRef<BinaryBasicBlock *> NewBlocks);
 
   /// Erase all blocks from the layout that are in ToErase. If this method
@@ -197,7 +195,7 @@
   void eraseBasicBlocks(const DenseSet<const BinaryBasicBlock *> ToErase);
 
   /// Make sure fragments' and basic blocks' indices match the current layout.
-  void updateLayoutIndices() const;
+  void updateLayoutIndices();
 
   /// Replace the current layout with NewLayout. Uses the block's
   /// self-identifying fragment number to assign blocks to infer function
@@ -208,12 +206,25 @@
   /// Clear layout releasing memory.
   void clear();
 
-  BinaryBasicBlock *getBlock(unsigned Index) const { return Blocks[Index]; }
+  BinaryBasicBlock *getBlock(unsigned Index) { return Blocks[Index]; }
+
+  const 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 *const BB,
+                                       const bool IgnoreSplits = true) {
+    return const_cast<BinaryBasicBlock *>(
+        static_cast<const FunctionLayout &>(*this).getBasicBlockAfter(
+            BB, IgnoreSplits));
+  }
 
   /// 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;
+  const BinaryBasicBlock *getBasicBlockAfter(const BinaryBasicBlock *BB,
+                                             bool IgnoreSplits = true) const;
 
   /// True if the layout contains at least two non-empty fragments.
   bool isSplit() const;
@@ -229,31 +240,54 @@
   bool isHotColdSplit() const { return fragment_size() <= 2; }
 
   size_t fragment_size() const {
-    assert(Fragments.size() >= 2 &&
+    assert(Fragments.size() >= 1 &&
            "Layout should have at least one fragment.");
-    return Fragments.size() - 1;
+    return Fragments.size();
   }
-  bool fragment_empty() const { return Fragments.size() == 1; }
-  const_iterator fragment_begin() const { return {FragmentNum(0), this}; }
-  const_iterator fragment_end() const {
-    return {FragmentNum(fragment_size()), this};
+  bool fragment_empty() const { return fragment_size() == 0; }
+
+  fragment_iterator fragment_begin() { return Fragments.begin(); }
+  fragment_const_iterator fragment_begin() const { return Fragments.begin(); }
+  fragment_iterator fragment_end() { return Fragments.end(); }
+  fragment_const_iterator fragment_end() const { return Fragments.end(); }
+  iterator_range<fragment_iterator> fragments() {
+    return {fragment_begin(), fragment_end()};
   }
-  iterator_range<const_iterator> fragments() const {
+  iterator_range<fragment_const_iterator> fragments() const {
     return {fragment_begin(), fragment_end()};
   }
 
   size_t block_size() const { return Blocks.size(); }
   bool block_empty() const { return Blocks.empty(); }
+
+  /// Required to return non-const qualified `BinaryBasicBlock *` for graph
+  /// traits.
   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(); }
+  const BinaryBasicBlock *block_back() const { return Blocks.back(); }
+
+  block_iterator block_begin() { return Blocks.begin(); }
+  block_const_iterator block_begin() const {
+    return block_const_iterator(Blocks.begin());
+  }
+  block_iterator block_end() { return Blocks.end(); }
+  block_const_iterator block_end() const {
+    return block_const_iterator(Blocks.end());
+  }
+  iterator_range<block_iterator> blocks() {
+    return {block_begin(), block_end()};
+  }
   iterator_range<block_const_iterator> blocks() const {
     return {block_begin(), block_end()};
   }
+  block_reverse_iterator block_rbegin() {
+    return block_reverse_iterator(block_end());
+  }
   block_const_reverse_iterator block_rbegin() const {
     return block_const_reverse_iterator(block_end());
   }
+  block_reverse_iterator block_rend() {
+    return block_reverse_iterator(block_begin());
+  }
   block_const_reverse_iterator block_rend() const {
     return block_const_reverse_iterator(block_begin());
   }
diff --git a/bolt/lib/Core/BinaryContext.cpp b/bolt/lib/Core/BinaryContext.cpp
--- a/bolt/lib/Core/BinaryContext.cpp
+++ b/bolt/lib/Core/BinaryContext.cpp
@@ -2199,7 +2199,7 @@
 
   using LabelRange = std::pair<const MCSymbol *, const MCSymbol *>;
   SmallVector<LabelRange> SplitLabels;
-  for (const FunctionFragment FF : BF.getLayout().getSplitFragments()) {
+  for (FunctionFragment &FF : BF.getLayout().getSplitFragments()) {
     MCSymbol *const SplitStartLabel = LocalCtx->createTempSymbol();
     MCSymbol *const SplitEndLabel = LocalCtx->createTempSymbol();
     SplitLabels.emplace_back(SplitStartLabel, SplitEndLabel);
diff --git a/bolt/lib/Core/BinaryEmitter.cpp b/bolt/lib/Core/BinaryEmitter.cpp
--- a/bolt/lib/Core/BinaryEmitter.cpp
+++ b/bolt/lib/Core/BinaryEmitter.cpp
@@ -129,7 +129,7 @@
 
   /// Emit function code. The caller is responsible for emitting function
   /// symbol(s) and setting the section to emit the code to.
-  void emitFunctionBody(BinaryFunction &BF, const FunctionFragment &FF,
+  void emitFunctionBody(BinaryFunction &BF, FunctionFragment &FF,
                         bool EmitCodeOnly = false);
 
 private:
@@ -137,7 +137,7 @@
   void emitFunctions();
 
   /// Emit a single function.
-  bool emitFunction(BinaryFunction &BF, const FunctionFragment &FF);
+  bool emitFunction(BinaryFunction &BF, FunctionFragment &FF);
 
   /// Helper for emitFunctionBody to write data inside a function
   /// (used for AArch64)
@@ -234,7 +234,7 @@
           !Function->hasValidProfile())
         Streamer.setAllowAutoPadding(false);
 
-      const FunctionLayout &Layout = Function->getLayout();
+      FunctionLayout &Layout = Function->getLayout();
       Emitted |= emitFunction(*Function, Layout.getMainFragment());
 
       if (Function->isSplit()) {
@@ -243,7 +243,7 @@
 
         assert((Layout.fragment_size() == 1 || Function->isSimple()) &&
                "Only simple functions can have fragments");
-        for (const FunctionFragment FF : Layout.getSplitFragments()) {
+        for (FunctionFragment &FF : Layout.getSplitFragments()) {
           // Skip empty fragments so no symbols and sections for empty fragments
           // are generated
           if (FF.empty() && !Function->hasConstantIsland())
@@ -280,7 +280,7 @@
 }
 
 bool BinaryEmitter::emitFunction(BinaryFunction &Function,
-                                 const FunctionFragment &FF) {
+                                 FunctionFragment &FF) {
   if (Function.size() == 0 && !Function.hasIslandsInfo())
     return false;
 
@@ -402,8 +402,7 @@
   return true;
 }
 
-void BinaryEmitter::emitFunctionBody(BinaryFunction &BF,
-                                     const FunctionFragment &FF,
+void BinaryEmitter::emitFunctionBody(BinaryFunction &BF, FunctionFragment &FF,
                                      bool EmitCodeOnly) {
   if (!EmitCodeOnly && FF.isSplitFragment() && BF.hasConstantIsland()) {
     assert(BF.getLayout().isHotColdSplit() &&
@@ -1160,7 +1159,7 @@
 }
 
 void emitFunctionBody(MCStreamer &Streamer, BinaryFunction &BF,
-                      const FunctionFragment &FF, bool EmitCodeOnly) {
+                      FunctionFragment &FF, bool EmitCodeOnly) {
   BinaryEmitter(Streamer, BF.getBinaryContext())
       .emitFunctionBody(BF, FF, EmitCodeOnly);
 }
diff --git a/bolt/lib/Core/BinaryFunction.cpp b/bolt/lib/Core/BinaryFunction.cpp
--- a/bolt/lib/Core/BinaryFunction.cpp
+++ b/bolt/lib/Core/BinaryFunction.cpp
@@ -513,7 +513,7 @@
   }
 
   StringRef SplitPointMsg = "";
-  for (const FunctionFragment FF : Layout.fragments()) {
+  for (const FunctionFragment &FF : Layout.fragments()) {
     OS << SplitPointMsg;
     SplitPointMsg = "-------   HOT-COLD SPLIT POINT   -------\n\n";
     for (const BinaryBasicBlock *BB : FF) {
@@ -2793,7 +2793,7 @@
 
   const char *Sep = "";
   (void)Sep;
-  for (const FunctionFragment FF : Layout.fragments()) {
+  for (FunctionFragment &FF : Layout.fragments()) {
     // Hot-cold border: at start of each region (with a different FDE) we need
     // to reset the CFI state.
     int32_t State = 0;
@@ -4119,7 +4119,7 @@
          "address (only in relocation mode)");
 
   BinaryBasicBlock *PrevBB = nullptr;
-  for (const FunctionFragment &FF : getLayout().fragments()) {
+  for (FunctionFragment &FF : getLayout().fragments()) {
     const uint64_t FragmentBaseAddress =
         getCodeSection(isSimple() ? FF.getFragmentNum() : FragmentNum::main())
             ->getOutputAddress();
diff --git a/bolt/lib/Core/Exceptions.cpp b/bolt/lib/Core/Exceptions.cpp
--- a/bolt/lib/Core/Exceptions.cpp
+++ b/bolt/lib/Core/Exceptions.cpp
@@ -367,7 +367,7 @@
     uint64_t Action;
   };
 
-  for (const FunctionFragment FF : getLayout().fragments()) {
+  for (FunctionFragment &FF : getLayout().fragments()) {
     // Sites to update - either regular or cold.
     CallSitesType &Sites = FF.isMainFragment() ? CallSites : ColdCallSites;
 
diff --git a/bolt/lib/Core/FunctionLayout.cpp b/bolt/lib/Core/FunctionLayout.cpp
--- a/bolt/lib/Core/FunctionLayout.cpp
+++ b/bolt/lib/Core/FunctionLayout.cpp
@@ -5,88 +5,162 @@
 #include <algorithm>
 #include <cstddef>
 #include <functional>
+#include <iterator>
+#include <memory>
 
 using namespace llvm;
 using namespace bolt;
 
-unsigned FunctionFragment::size() const { return end() - begin(); }
-bool FunctionFragment::empty() const { return end() == begin(); }
+FunctionFragment::FunctionFragment(FunctionLayout &Layout,
+                                   const FragmentNum Num)
+    : Layout(&Layout), Num(Num), StartIndex(Layout.block_size()) {}
+
+FunctionFragment::iterator FunctionFragment::begin() {
+  return iterator(Layout->block_begin() + StartIndex);
+}
 FunctionFragment::const_iterator FunctionFragment::begin() const {
-  return Layout.block_begin() + Layout.Fragments[Num.get()];
+  return const_iterator(Layout->block_begin() + StartIndex);
+}
+FunctionFragment::iterator FunctionFragment::end() {
+  return iterator(Layout->block_begin() + StartIndex + Size);
 }
 FunctionFragment::const_iterator FunctionFragment::end() const {
-  return Layout.block_begin() + Layout.Fragments[Num.get() + 1];
+  return const_iterator(Layout->block_begin() + StartIndex + Size);
+}
+
+const BinaryBasicBlock *FunctionFragment::front() const { return *begin(); }
+
+FunctionLayout::FunctionLayout() { addFragment(); }
+
+FunctionLayout::FunctionLayout(const FunctionLayout &Other)
+    : Blocks(Other.Blocks) {
+  for (FunctionFragment *const FF : Other.Fragments) {
+    auto *Copy = new FunctionFragment(*FF);
+    Copy->Layout = this;
+    Fragments.emplace_back(Copy);
+  }
+}
+
+FunctionLayout::FunctionLayout(FunctionLayout &&Other)
+    : Fragments(std::move(Other.Fragments)), Blocks(std::move(Other.Blocks)) {
+  for (FunctionFragment *const F : Fragments)
+    F->Layout = this;
+}
+
+FunctionLayout &FunctionLayout::operator=(const FunctionLayout &Other) {
+  Blocks = Other.Blocks;
+  for (FunctionFragment *const FF : Other.Fragments) {
+    auto *const Copy = new FunctionFragment(*FF);
+    Copy->Layout = this;
+    Fragments.emplace_back(Copy);
+  }
+  return *this;
+}
+
+FunctionLayout &FunctionLayout::operator=(FunctionLayout &&Other) {
+  Fragments = std::move(Other.Fragments);
+  Blocks = std::move(Other.Blocks);
+  for (FunctionFragment *const FF : Fragments)
+    FF->Layout = this;
+  return *this;
+}
+
+FunctionLayout::~FunctionLayout() {
+  for (FunctionFragment *const F : Fragments) {
+    delete F;
+  }
+}
+
+FunctionFragment &FunctionLayout::addFragment() {
+  FunctionFragment *const FF =
+      new FunctionFragment(*this, FragmentNum(Fragments.size()));
+  Fragments.emplace_back(FF);
+  return *FF;
 }
-BinaryBasicBlock *FunctionFragment::front() const { return *begin(); }
 
-FunctionFragment FunctionLayout::addFragment() {
-  Fragments.emplace_back(Blocks.size());
-  return getFragment(FragmentNum(Blocks.size() - 1));
+FunctionFragment &FunctionLayout::getFragment(FragmentNum Num) {
+  return *Fragments[Num.get()];
 }
 
-FunctionFragment FunctionLayout::getFragment(FragmentNum Num) const {
-  return FunctionFragment(Num, *this);
+const FunctionFragment &FunctionLayout::getFragment(FragmentNum Num) const {
+  return *Fragments[Num.get()];
 }
 
-FunctionFragment
-FunctionLayout::findFragment(const BinaryBasicBlock *BB) const {
+const FunctionFragment &
+FunctionLayout::findFragment(const BinaryBasicBlock *const BB) const {
   return getFragment(BB->getFragmentNum());
 }
 
-void FunctionLayout::addBasicBlock(BinaryBasicBlock *BB) {
+void FunctionLayout::addBasicBlock(BinaryBasicBlock *const BB) {
   BB->setLayoutIndex(Blocks.size());
   Blocks.emplace_back(BB);
-  ++Fragments.back();
-  assert(Fragments.back() == Blocks.size());
+  Fragments.back()->Size++;
 }
 
-void FunctionLayout::insertBasicBlocks(BinaryBasicBlock *InsertAfter,
-                                       ArrayRef<BinaryBasicBlock *> NewBlocks) {
-  const block_iterator InsertBeforePos =
-      InsertAfter ? std::next(findBasicBlockPos(InsertAfter)) : Blocks.begin();
-  Blocks.insert(InsertBeforePos, NewBlocks.begin(), NewBlocks.end());
+void FunctionLayout::insertBasicBlocks(
+    const BinaryBasicBlock *const InsertAfter,
+    const ArrayRef<BinaryBasicBlock *> NewBlocks) {
+  block_iterator InsertBeforePos = Blocks.begin();
+  FragmentNum InsertFragmentNum = FragmentNum::main();
+  unsigned LayoutIndex = 0;
+
+  if (InsertAfter) {
+    InsertBeforePos = std::next(findBasicBlockPos(InsertAfter));
+    InsertFragmentNum = InsertAfter->getFragmentNum();
+    LayoutIndex = InsertAfter->getLayoutIndex();
+  }
+
+  llvm::copy(NewBlocks, std::inserter(Blocks, InsertBeforePos));
+
+  for (BinaryBasicBlock *const BB : NewBlocks) {
+    BB->setFragmentNum(InsertFragmentNum);
+    BB->setLayoutIndex(LayoutIndex++);
+  }
+
+  const fragment_iterator InsertFragment =
+      fragment_begin() + InsertFragmentNum.get();
+  InsertFragment->Size += NewBlocks.size();
 
-  unsigned FragmentUpdateStart =
-      InsertAfter ? InsertAfter->getFragmentNum().get() + 1 : 1;
-  std::for_each(
-      Fragments.begin() + FragmentUpdateStart, Fragments.end(),
-      [&](unsigned &FragmentOffset) { FragmentOffset += NewBlocks.size(); });
+  const fragment_iterator TailBegin = std::next(InsertFragment);
+  auto const UpdateFragment = [&](FunctionFragment &FF) {
+    FF.StartIndex += NewBlocks.size();
+    for (BinaryBasicBlock *const BB : FF)
+      BB->setLayoutIndex(LayoutIndex++);
+  };
+  std::for_each(TailBegin, fragment_end(), UpdateFragment);
 }
 
 void FunctionLayout::eraseBasicBlocks(
     const DenseSet<const BinaryBasicBlock *> ToErase) {
-  auto IsErased = [&](const BinaryBasicBlock *const BB) {
+  const auto IsErased = [&](const BinaryBasicBlock *const BB) {
     return ToErase.contains(BB);
   };
-  FragmentListType NewFragments;
-  NewFragments.emplace_back(0);
-  for (const FunctionFragment FF : fragments()) {
-    unsigned ErasedBlocks = count_if(FF, IsErased);
-    // Only add the fragment if it is non-empty after removing blocks.
-    unsigned NewFragment = NewFragments.back() + FF.size() - ErasedBlocks;
-    NewFragments.emplace_back(NewFragment);
+
+  unsigned TotalErased = 0;
+  for (FunctionFragment &FF : fragments()) {
+    unsigned Erased = count_if(FF, IsErased);
+    FF.Size -= Erased;
+    FF.StartIndex -= TotalErased;
+    TotalErased += Erased;
   }
   llvm::erase_if(Blocks, IsErased);
-  Fragments = std::move(NewFragments);
 
   // Remove empty fragments at the end
-  const_iterator EmptyTailBegin =
-      llvm::find_if_not(reverse(fragments()), [](const FunctionFragment &FF) {
-        return FF.empty();
-      }).base();
-  if (EmptyTailBegin != fragment_end()) {
-    // Add +1 for one-past-the-end entry
-    const FunctionFragment TailBegin = *EmptyTailBegin;
-    unsigned NewFragmentSize = TailBegin.getFragmentNum().get() + 1;
-    Fragments.resize(NewFragmentSize);
-  }
+  const auto IsEmpty = [](const FunctionFragment *const FF) {
+    return FF->empty();
+  };
+  const FragmentListType::iterator EmptyTailBegin =
+      llvm::find_if_not(reverse(Fragments), IsEmpty).base();
+  std::for_each(EmptyTailBegin, Fragments.end(),
+                [](FunctionFragment *const FF) { delete FF; });
+  Fragments.erase(EmptyTailBegin, Fragments.end());
 
   updateLayoutIndices();
 }
 
-void FunctionLayout::updateLayoutIndices() const {
+void FunctionLayout::updateLayoutIndices() {
   unsigned BlockIndex = 0;
-  for (const FunctionFragment FF : fragments()) {
+  for (FunctionFragment &FF : fragments()) {
     for (BinaryBasicBlock *const BB : FF) {
       BB->setLayoutIndex(BlockIndex++);
       BB->setFragmentNum(FF.getFragmentNum());
@@ -98,7 +172,7 @@
   const bool EqualBlockOrder = llvm::equal(Blocks, NewLayout);
   if (EqualBlockOrder) {
     const bool EqualPartitioning =
-        llvm::all_of(fragments(), [](const FunctionFragment FF) {
+        llvm::all_of(fragments(), [](const FunctionFragment &FF) {
           return llvm::all_of(FF, [&](const BinaryBasicBlock *const BB) {
             return FF.Num == BB->getFragmentNum();
           });
@@ -107,43 +181,44 @@
       return false;
   }
 
-  Blocks = BasicBlockListType(NewLayout.begin(), NewLayout.end());
-  Fragments = {0, 0};
+  clear();
 
   // Generate fragments
-  for (const auto &BB : enumerate(Blocks)) {
-    unsigned FragmentNum = BB.value()->getFragmentNum().get();
+  for (BinaryBasicBlock *const BB : NewLayout) {
+    FragmentNum Num = BB->getFragmentNum();
 
-    assert(FragmentNum >= fragment_size() - 1 &&
+    assert(Num >= Fragments.back()->getFragmentNum() &&
            "Blocks must be arranged such that fragments are monotonically "
            "increasing.");
 
     // Add empty fragments if necessary
-    for (unsigned I = fragment_size(); I <= FragmentNum; ++I) {
+    while (Fragments.back()->getFragmentNum() < Num)
       addFragment();
-      Fragments[I] = BB.index();
-    }
 
     // Set the next fragment to point one past the current BB
-    Fragments[FragmentNum + 1] = BB.index() + 1;
+    addBasicBlock(BB);
   }
 
   return true;
 }
 
 void FunctionLayout::clear() {
-  Blocks = {};
-  Fragments = {0, 0};
-}
-
-BinaryBasicBlock *FunctionLayout::getBasicBlockAfter(const BinaryBasicBlock *BB,
-                                                     bool IgnoreSplits) const {
-  const block_const_iterator BBPos = find(Blocks, BB);
-  if (BBPos == Blocks.end())
+  Blocks = BasicBlockListType();
+  for (FunctionFragment *const FF : Fragments)
+    delete FF;
+  Fragments = FragmentListType();
+  addFragment();
+}
+
+const BinaryBasicBlock *
+FunctionLayout::getBasicBlockAfter(const BinaryBasicBlock *BB,
+                                   bool IgnoreSplits) const {
+  const block_const_iterator BBPos = find(blocks(), BB);
+  if (BBPos == block_end())
     return nullptr;
 
   const block_const_iterator BlockAfter = std::next(BBPos);
-  if (BlockAfter == Blocks.end())
+  if (BlockAfter == block_end())
     return nullptr;
 
   if (!IgnoreSplits)
@@ -154,7 +229,7 @@
 }
 
 bool FunctionLayout::isSplit() const {
-  unsigned NonEmptyFragCount = llvm::count_if(
+  const unsigned NonEmptyFragCount = llvm::count_if(
       fragments(), [](const FunctionFragment &FF) { return !FF.empty(); });
   return NonEmptyFragCount >= 2;
 }
@@ -166,7 +241,7 @@
 
 FunctionLayout::block_const_iterator
 FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) const {
-  return find(Blocks, BB);
+  return block_const_iterator(find(Blocks, BB));
 }
 
 FunctionLayout::block_iterator
diff --git a/bolt/lib/Passes/BinaryPasses.cpp b/bolt/lib/Passes/BinaryPasses.cpp
--- a/bolt/lib/Passes/BinaryPasses.cpp
+++ b/bolt/lib/Passes/BinaryPasses.cpp
@@ -593,7 +593,7 @@
   for (auto &It : BC.getBinaryFunctions()) {
     BinaryFunction &BF = It.second;
 
-    for (const FunctionFragment FF : BF.getLayout().fragments()) {
+    for (FunctionFragment &FF : BF.getLayout().fragments()) {
       int64_t CurrentGnuArgsSize = 0;
 
       for (BinaryBasicBlock *const BB : FF) {
diff --git a/bolt/lib/Rewrite/RewriteInstance.cpp b/bolt/lib/Rewrite/RewriteInstance.cpp
--- a/bolt/lib/Rewrite/RewriteInstance.cpp
+++ b/bolt/lib/Rewrite/RewriteInstance.cpp
@@ -3183,7 +3183,7 @@
       BC->deregisterSection(*Section);
     assert(Function->getOriginSectionName() && "expected origin section");
     Function->CodeSectionName = Function->getOriginSectionName()->str();
-    for (const FunctionFragment FF :
+    for (const FunctionFragment &FF :
          Function->getLayout().getSplitFragments()) {
       if (ErrorOr<BinarySection &> ColdSection =
               Function->getCodeSection(FF.getFragmentNum()))
@@ -3726,7 +3726,8 @@
     if (!Function.isSplit())
       continue;
 
-    for (const FunctionFragment FF : Function.getLayout().getSplitFragments()) {
+    for (const FunctionFragment &FF :
+         Function.getLayout().getSplitFragments()) {
       ErrorOr<BinarySection &> ColdSection =
           Function.getCodeSection(FF.getFragmentNum());
       assert(ColdSection && "cannot find section for cold part");
@@ -4518,7 +4519,7 @@
       Symbols.emplace_back(ICFSymbol);
     }
     if (Function.isSplit() && Function.cold().getAddress()) {
-      for (const FunctionFragment FF :
+      for (const FunctionFragment &FF :
            Function.getLayout().getSplitFragments()) {
         ELFSymTy NewColdSym = FunctionSymbol;
         const SmallString<256> SymbolName = formatv(