bolt/lib/Core/FunctionLayout.cpp

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