bolt/lib/Core/FunctionLayout.cpp

   1 //===- bolt/Core/FunctionLayout.cpp - Fragmented Function Layout -*- C++ -*-==//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "bolt/Core/FunctionLayout.h"
  10 #include "bolt/Core/BinaryBasicBlock.h"
  11 #include "llvm/ADT/STLExtras.h"
  12 #include "llvm/ADT/edit_distance.h"
  13 #include <algorithm>
  14 #include <iterator>
  15
  16 using namespace llvm;
  17 using namespace bolt;
  18
  19 FunctionFragment::FunctionFragment(FunctionLayout &Layout,
  20                                    const FragmentNum Num)
  21     : Layout(&Layout), Num(Num), StartIndex(Layout.block_size()) {}
  22
  23 FunctionFragment::iterator FunctionFragment::begin() {
  24   return iterator(Layout->block_begin() + StartIndex);
  25 }
  26 FunctionFragment::const_iterator FunctionFragment::begin() const {
  27   return const_iterator(Layout->block_begin() + StartIndex);
  28 }
  29 FunctionFragment::iterator FunctionFragment::end() {
  30   return iterator(Layout->block_begin() + StartIndex + Size);
  31 }
  32 FunctionFragment::const_iterator FunctionFragment::end() const {
  33   return const_iterator(Layout->block_begin() + StartIndex + Size);
  34 }
  35
  36 BinaryBasicBlock *FunctionFragment::front() const { return *begin(); }
  37
  38 BinaryBasicBlock *FunctionFragment::back() const { return *std::prev(end()); }
  39
  40 FunctionLayout::FunctionLayout() { addFragment(); }
  41
  42 FunctionLayout::FunctionLayout(const FunctionLayout &Other)
  43     : Blocks(Other.Blocks) {
  44   for (FunctionFragment *const FF : Other.Fragments) {
  45     auto *Copy = new FunctionFragment(*FF);
  46     Copy->Layout = this;
  47     Fragments.emplace_back(Copy);
  48   }
  49 }
  50
  51 FunctionLayout::FunctionLayout(FunctionLayout &&Other)
  52     : Fragments(std::move(Other.Fragments)), Blocks(std::move(Other.Blocks)) {
  53   for (FunctionFragment *const F : Fragments)
  54     F->Layout = this;
  55 }
  56
  57 FunctionLayout &FunctionLayout::operator=(const FunctionLayout &Other) {
  58   Blocks = Other.Blocks;
  59   for (FunctionFragment *const FF : Other.Fragments) {
  60     auto *const Copy = new FunctionFragment(*FF);
  61     Copy->Layout = this;
  62     Fragments.emplace_back(Copy);
  63   }
  64   return *this;
  65 }
  66
  67 FunctionLayout &FunctionLayout::operator=(FunctionLayout &&Other) {
  68   Fragments = std::move(Other.Fragments);
  69   Blocks = std::move(Other.Blocks);
  70   for (FunctionFragment *const FF : Fragments)
  71     FF->Layout = this;
  72   return *this;
  73 }
  74
  75 FunctionLayout::~FunctionLayout() {
  76   for (FunctionFragment *const F : Fragments) {
  77     delete F;
  78   }
  79 }
  80
  81 FunctionFragment &FunctionLayout::addFragment() {
  82   FunctionFragment *const FF =
  83       new FunctionFragment(*this, FragmentNum(Fragments.size()));
  84   Fragments.emplace_back(FF);
  85   return *FF;
  86 }
  87
  88 FunctionFragment &FunctionLayout::getFragment(FragmentNum Num) {
  89   return *Fragments[Num.get()];
  90 }
  91
  92 const FunctionFragment &FunctionLayout::getFragment(FragmentNum Num) const {
  93   return *Fragments[Num.get()];
  94 }
  95
  96 const FunctionFragment &
  97 FunctionLayout::findFragment(const BinaryBasicBlock *const BB) const {
  98   return getFragment(BB->getFragmentNum());
  99 }
 100
 101 void FunctionLayout::addBasicBlock(BinaryBasicBlock *const BB) {
 102   BB->setLayoutIndex(Blocks.size());
 103   Blocks.emplace_back(BB);
 104   Fragments.back()->Size++;
 105 }
 106
 107 void FunctionLayout::insertBasicBlocks(
 108     const BinaryBasicBlock *const InsertAfter,
 109     const ArrayRef<BinaryBasicBlock *> NewBlocks) {
 110   block_iterator InsertBeforePos = Blocks.begin();
 111   FragmentNum InsertFragmentNum = FragmentNum::main();
 112   unsigned LayoutIndex = 0;
 113
 114   if (InsertAfter) {
 115     InsertBeforePos = std::next(findBasicBlockPos(InsertAfter));
 116     InsertFragmentNum = InsertAfter->getFragmentNum();
 117     LayoutIndex = InsertAfter->getLayoutIndex();
 118   }
 119
 120   llvm::copy(NewBlocks, std::inserter(Blocks, InsertBeforePos));
 121
 122   for (BinaryBasicBlock *const BB : NewBlocks) {
 123     BB->setFragmentNum(InsertFragmentNum);
 124     BB->setLayoutIndex(LayoutIndex++);
 125   }
 126
 127   const fragment_iterator InsertFragment =
 128       fragment_begin() + InsertFragmentNum.get();
 129   InsertFragment->Size += NewBlocks.size();
 130
 131   const fragment_iterator TailBegin = std::next(InsertFragment);
 132   auto const UpdateFragment = [&](FunctionFragment &FF) {
 133     FF.StartIndex += NewBlocks.size();
 134     for (BinaryBasicBlock *const BB : FF)
 135       BB->setLayoutIndex(LayoutIndex++);
 136   };
 137   std::for_each(TailBegin, fragment_end(), UpdateFragment);
 138 }
 139
 140 void FunctionLayout::eraseBasicBlocks(
 141     const DenseSet<const BinaryBasicBlock *> ToErase) {
 142   const auto IsErased = [&](const BinaryBasicBlock *const BB) {
 143     return ToErase.contains(BB);
 144   };
 145
 146   unsigned TotalErased = 0;
 147   for (FunctionFragment &FF : fragments()) {
 148     unsigned Erased = count_if(FF, IsErased);
 149     FF.Size -= Erased;
 150     FF.StartIndex -= TotalErased;
 151     TotalErased += Erased;
 152   }
 153   llvm::erase_if(Blocks, IsErased);
 154
 155   // Remove empty fragments at the end
 156   const auto IsEmpty = [](const FunctionFragment *const FF) {
 157     return FF->empty();
 158   };
 159   const FragmentListType::iterator EmptyTailBegin =
 160       llvm::find_if_not(reverse(Fragments), IsEmpty).base();
 161   for (FunctionFragment *const FF :
 162        llvm::make_range(EmptyTailBegin, Fragments.end()))
 163     delete FF;
 164   Fragments.erase(EmptyTailBegin, Fragments.end());
 165
 166   updateLayoutIndices();
 167 }
 168
 169 void FunctionLayout::updateLayoutIndices() const {
 170   unsigned BlockIndex = 0;
 171   for (const FunctionFragment &FF : fragments()) {
 172     for (BinaryBasicBlock *const BB : FF) {
 173       BB->setLayoutIndex(BlockIndex++);
 174       BB->setFragmentNum(FF.getFragmentNum());
 175     }
 176   }
 177 }
 178 void FunctionLayout::updateLayoutIndices(
 179     ArrayRef<BinaryBasicBlock *> Order) const {
 180   for (auto [Index, BB] : llvm::enumerate(Order))
 181     BB->setLayoutIndex(Index);
 182 }
 183
 184 bool FunctionLayout::update(const ArrayRef<BinaryBasicBlock *> NewLayout) {
 185   const bool EqualBlockOrder = llvm::equal(Blocks, NewLayout);
 186   if (EqualBlockOrder) {
 187     const bool EqualPartitioning =
 188         llvm::all_of(fragments(), [](const FunctionFragment &FF) {
 189           return llvm::all_of(FF, [&](const BinaryBasicBlock *const BB) {
 190             return FF.Num == BB->getFragmentNum();
 191           });
 192         });
 193     if (EqualPartitioning)
 194       return false;
 195   }
 196
 197   clear();
 198
 199   // Generate fragments
 200   for (BinaryBasicBlock *const BB : NewLayout) {
 201     FragmentNum Num = BB->getFragmentNum();
 202
 203     // Add empty fragments if necessary
 204     while (Fragments.back()->getFragmentNum() < Num)
 205       addFragment();
 206
 207     // Set the next fragment to point one past the current BB
 208     addBasicBlock(BB);
 209   }
 210
 211   return true;
 212 }
 213
 214 void FunctionLayout::clear() {
 215   Blocks = BasicBlockListType();
 216   // If the binary does not have relocations and is not split, the function will
 217   // be written to the output stream at its original file offset (see
 218   // `RewriteInstance::rewriteFile`). Hence, when the layout is cleared, retain
 219   // the main fragment, so that this information is not lost.
 220   for (FunctionFragment *const FF : llvm::drop_begin(Fragments))
 221     delete FF;
 222   Fragments = FragmentListType{Fragments.front()};
 223   getMainFragment().Size = 0;
 224 }
 225
 226 const BinaryBasicBlock *
 227 FunctionLayout::getBasicBlockAfter(const BinaryBasicBlock *BB,
 228                                    bool IgnoreSplits) const {
 229   const block_const_iterator BBPos = find(blocks(), BB);
 230   if (BBPos == block_end())
 231     return nullptr;
 232
 233   const block_const_iterator BlockAfter = std::next(BBPos);
 234   if (BlockAfter == block_end())
 235     return nullptr;
 236
 237   if (!IgnoreSplits)
 238     if (BlockAfter == getFragment(BB->getFragmentNum()).end())
 239       return nullptr;
 240
 241   return *BlockAfter;
 242 }
 243
 244 bool FunctionLayout::isSplit() const {
 245   const unsigned NonEmptyFragCount = llvm::count_if(
 246       fragments(), [](const FunctionFragment &FF) { return !FF.empty(); });
 247   return NonEmptyFragCount >= 2;
 248 }
 249
 250 uint64_t FunctionLayout::getEditDistance(
 251     const ArrayRef<const BinaryBasicBlock *> OldBlockOrder) const {
 252   return ComputeEditDistance<const BinaryBasicBlock *>(OldBlockOrder, Blocks);
 253 }
 254
 255 FunctionLayout::block_const_iterator
 256 FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) const {
 257   return block_const_iterator(find(Blocks, BB));
 258 }
 259
 260 FunctionLayout::block_iterator
 261 FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) {
 262   return find(Blocks, BB);
 263 }