From 101344af1af82d1633c773b718788eaa813d7f79 Mon Sep 17 00:00:00 2001 From: Fabian Parzefall Date: Wed, 24 Aug 2022 10:02:35 -0700 Subject: [PATCH] [BOLT] Allocate FunctionFragment on heap This changes `FunctionFragment` from being used as a temporary proxy object to access basic block ranges to a heap-allocated object that can store fragment-specific information. Reviewed By: rafauler Differential Revision: https://reviews.llvm.org/D132050 --- bolt/include/bolt/Core/BinaryEmitter.h | 2 +- bolt/include/bolt/Core/FunctionLayout.h | 192 ++++++++++++++++------------- bolt/lib/Core/BinaryContext.cpp | 2 +- bolt/lib/Core/BinaryEmitter.cpp | 15 ++- bolt/lib/Core/BinaryFunction.cpp | 6 +- bolt/lib/Core/Exceptions.cpp | 2 +- bolt/lib/Core/FunctionLayout.cpp | 209 ++++++++++++++++++++++---------- bolt/lib/Passes/BinaryPasses.cpp | 2 +- bolt/lib/Rewrite/RewriteInstance.cpp | 7 +- 9 files changed, 271 insertions(+), 166 deletions(-) diff --git a/bolt/include/bolt/Core/BinaryEmitter.h b/bolt/include/bolt/Core/BinaryEmitter.h index 80dab4b..8c3e4b8 100644 --- a/bolt/include/bolt/Core/BinaryEmitter.h +++ b/bolt/include/bolt/Core/BinaryEmitter.h @@ -35,7 +35,7 @@ void emitBinaryContext(MCStreamer &Streamer, BinaryContext &BC, /// 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 index 98d189b..0917350 100644 --- a/bolt/include/bolt/Core/FunctionLayout.h +++ b/bolt/include/bolt/Core/FunctionLayout.h @@ -24,6 +24,8 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/iterator.h" #include "llvm/ADT/iterator_range.h" +#include +#include namespace llvm { namespace bolt { @@ -69,28 +71,41 @@ class FunctionFragment { using FragmentListType = SmallVector; public: - using const_iterator = BasicBlockListType::const_iterator; + using iterator = raw_pointer_iterator; + using const_iterator = + raw_pointer_iterator; 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 @@ -103,94 +118,76 @@ public: /// iterating either over fragments or over BinaryFunction::begin()..end(). class FunctionLayout { private: + using FragmentListType = SmallVector; using BasicBlockListType = SmallVector; using block_iterator = BasicBlockListType::iterator; - using FragmentListType = SmallVector; 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) { - 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; + using fragment_const_iterator = + pointee_iterator; + using block_const_iterator = + raw_pointer_iterator; + using block_reverse_iterator = std::reverse_iterator; using block_const_reverse_iterator = - BasicBlockListType::const_reverse_iterator; + std::reverse_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); /// Return the fragment identified by Num. - FunctionFragment getFragment(FragmentNum Num) const; + 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 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 getSplitFragments() { + return {++fragment_begin(), fragment_end()}; + } + + /// Get the fragment that contains all entry blocks and other blocks that + /// cannot be split. + iterator_range 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 NewBlocks); /// Erase all blocks from the layout that are in ToErase. If this method @@ -198,7 +195,7 @@ public: void eraseBasicBlocks(const DenseSet 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 @@ -209,12 +206,25 @@ public: /// 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( + static_cast(*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; @@ -230,29 +240,49 @@ public: 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 fragments() { + return {fragment_begin(), fragment_end()}; } - iterator_range fragments() const { + iterator_range 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 blocks() { + return {block_begin(), block_end()}; + } iterator_range blocks() const { return {block_begin(), block_end()}; } + + block_reverse_iterator block_rbegin() { return Blocks.rbegin(); } block_const_reverse_iterator block_rbegin() const { return Blocks.rbegin(); } + block_reverse_iterator block_rend() { return Blocks.rend(); } block_const_reverse_iterator block_rend() const { return Blocks.rend(); } iterator_range rblocks() const { return {block_rbegin(), block_rend()}; diff --git a/bolt/lib/Core/BinaryContext.cpp b/bolt/lib/Core/BinaryContext.cpp index a1689dc..5cef2ae 100644 --- a/bolt/lib/Core/BinaryContext.cpp +++ b/bolt/lib/Core/BinaryContext.cpp @@ -2199,7 +2199,7 @@ BinaryContext::calculateEmittedSize(BinaryFunction &BF, bool FixBranches) { using LabelRange = std::pair; SmallVector 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 index 09a0ae9..8061601 100644 --- a/bolt/lib/Core/BinaryEmitter.cpp +++ b/bolt/lib/Core/BinaryEmitter.cpp @@ -129,7 +129,7 @@ public: /// 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 @@ private: 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 @@ void BinaryEmitter::emitFunctions() { !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 @@ void BinaryEmitter::emitFunctions() { 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 @@ void BinaryEmitter::emitFunctions() { } bool BinaryEmitter::emitFunction(BinaryFunction &Function, - const FunctionFragment &FF) { + FunctionFragment &FF) { if (Function.size() == 0 && !Function.hasIslandsInfo()) return false; @@ -402,8 +402,7 @@ bool BinaryEmitter::emitFunction(BinaryFunction &Function, 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 emitBinaryContext(MCStreamer &Streamer, BinaryContext &BC, } 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 index 446af11..6bd06f0 100644 --- a/bolt/lib/Core/BinaryFunction.cpp +++ b/bolt/lib/Core/BinaryFunction.cpp @@ -513,7 +513,7 @@ void BinaryFunction::print(raw_ostream &OS, std::string Annotation, } 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 @@ bool BinaryFunction::finalizeCFIState() { 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 @@ void BinaryFunction::updateOutputValues(const MCAsmLayout &Layout) { "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 index 6cbe393..416e0cd 100644 --- a/bolt/lib/Core/Exceptions.cpp +++ b/bolt/lib/Core/Exceptions.cpp @@ -367,7 +367,7 @@ void BinaryFunction::updateEHRanges() { 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 index d5dfab0..d37c430 100644 --- a/bolt/lib/Core/FunctionLayout.cpp +++ b/bolt/lib/Core/FunctionLayout.cpp @@ -5,88 +5,162 @@ #include #include #include +#include +#include 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 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 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 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 @@ bool FunctionLayout::update(const ArrayRef NewLayout) { 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 @@ bool FunctionLayout::update(const ArrayRef NewLayout) { 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 @@ BinaryBasicBlock *FunctionLayout::getBasicBlockAfter(const BinaryBasicBlock *BB, } 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 @@ uint64_t FunctionLayout::getEditDistance( 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 index 2d3c68e..3c815aa 100644 --- a/bolt/lib/Passes/BinaryPasses.cpp +++ b/bolt/lib/Passes/BinaryPasses.cpp @@ -593,7 +593,7 @@ void LowerAnnotations::runOnFunctions(BinaryContext &BC) { 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 index 88dd6d9..6b050db 100644 --- a/bolt/lib/Rewrite/RewriteInstance.cpp +++ b/bolt/lib/Rewrite/RewriteInstance.cpp @@ -3183,7 +3183,7 @@ void RewriteInstance::emitAndLink() { 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 ColdSection = Function->getCodeSection(FF.getFragmentNum())) @@ -3726,7 +3726,8 @@ void RewriteInstance::mapCodeSections(RuntimeDyld &RTDyld) { if (!Function.isSplit()) continue; - for (const FunctionFragment FF : Function.getLayout().getSplitFragments()) { + for (const FunctionFragment &FF : + Function.getLayout().getSplitFragments()) { ErrorOr ColdSection = Function.getCodeSection(FF.getFragmentNum()); assert(ColdSection && "cannot find section for cold part"); @@ -4518,7 +4519,7 @@ void RewriteInstance::updateELFSymbolTable( 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( -- 2.7.4