270 lines · 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-exception6//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 16using namespace llvm;17using namespace bolt;18 19FunctionFragment::FunctionFragment(FunctionLayout &Layout,20 const FragmentNum Num)21 : Layout(&Layout), Num(Num), StartIndex(Layout.block_size()) {}22 23FunctionFragment::iterator FunctionFragment::begin() {24 return iterator(Layout->block_begin() + StartIndex);25}26FunctionFragment::const_iterator FunctionFragment::begin() const {27 return const_iterator(Layout->block_begin() + StartIndex);28}29FunctionFragment::iterator FunctionFragment::end() {30 return iterator(Layout->block_begin() + StartIndex + Size);31}32FunctionFragment::const_iterator FunctionFragment::end() const {33 return const_iterator(Layout->block_begin() + StartIndex + Size);34}35 36BinaryBasicBlock *FunctionFragment::front() const { return *begin(); }37 38BinaryBasicBlock *FunctionFragment::back() const { return *std::prev(end()); }39 40FunctionLayout::FunctionLayout() { addFragment(); }41 42FunctionLayout::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 51FunctionLayout::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 57FunctionLayout &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 67FunctionLayout &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 75FunctionLayout::~FunctionLayout() {76 for (FunctionFragment *const F : Fragments) {77 delete F;78 }79}80 81FunctionFragment &FunctionLayout::addFragment() {82 FunctionFragment *const FF =83 new FunctionFragment(*this, FragmentNum(Fragments.size()));84 Fragments.emplace_back(FF);85 return *FF;86}87 88FunctionFragment &FunctionLayout::getFragment(FragmentNum Num) {89 return *Fragments[Num.get()];90}91 92const FunctionFragment &FunctionLayout::getFragment(FragmentNum Num) const {93 return *Fragments[Num.get()];94}95 96const FunctionFragment &97FunctionLayout::findFragment(const BinaryBasicBlock *const BB) const {98 return getFragment(BB->getFragmentNum());99}100 101void FunctionLayout::addBasicBlock(BinaryBasicBlock *const BB) {102 BB->setLayoutIndex(Blocks.size());103 Blocks.emplace_back(BB);104 Fragments.back()->Size++;105}106 107void 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 140void 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 end156 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 169void 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}178void FunctionLayout::updateLayoutIndices(179 ArrayRef<BinaryBasicBlock *> Order) const {180 for (auto [Index, BB] : llvm::enumerate(Order))181 BB->setLayoutIndex(Index);182}183 184bool 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 fragments200 for (BinaryBasicBlock *const BB : NewLayout) {201 FragmentNum Num = BB->getFragmentNum();202 203 // Add empty fragments if necessary204 while (Fragments.back()->getFragmentNum() < Num)205 addFragment();206 207 // Set the next fragment to point one past the current BB208 addBasicBlock(BB);209 }210 211 return true;212}213 214void FunctionLayout::clear() {215 Blocks = BasicBlockListType();216 // If the binary does not have relocations and is not split, the function will217 // be written to the output stream at its original file offset (see218 // `RewriteInstance::rewriteFile`). Hence, when the layout is cleared, retain219 // 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 226const BinaryBasicBlock *227FunctionLayout::getBasicBlockAfter(block_const_iterator BBIter,228 bool IgnoreSplits) const {229 const block_const_iterator BlockAfter = std::next(BBIter);230 if (BlockAfter == block_end())231 return nullptr;232 233 if (!IgnoreSplits)234 if (BlockAfter == getFragment((*BBIter)->getFragmentNum()).end())235 return nullptr;236 237 return *BlockAfter;238}239 240const BinaryBasicBlock *241FunctionLayout::getBasicBlockAfter(const BinaryBasicBlock *BB,242 bool IgnoreSplits) const {243 const block_const_iterator BBPos = find(blocks(), BB);244 if (BBPos == block_end())245 return nullptr;246 247 return getBasicBlockAfter(BBPos, IgnoreSplits);248}249 250bool FunctionLayout::isSplit() const {251 const unsigned NonEmptyFragCount = llvm::count_if(252 fragments(), [](const FunctionFragment &FF) { return !FF.empty(); });253 return NonEmptyFragCount >= 2;254}255 256uint64_t FunctionLayout::getEditDistance(257 const ArrayRef<const BinaryBasicBlock *> OldBlockOrder) const {258 return ComputeEditDistance<const BinaryBasicBlock *>(OldBlockOrder, Blocks);259}260 261FunctionLayout::block_const_iterator262FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) const {263 return block_const_iterator(find(Blocks, BB));264}265 266FunctionLayout::block_iterator267FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) {268 return find(Blocks, BB);269}270