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 9 using namespace llvm; 10 using namespace bolt; 11 12 unsigned FunctionFragment::size() const { return end() - begin(); } 13 bool FunctionFragment::empty() const { return end() == begin(); } 14 FunctionFragment::const_iterator FunctionFragment::begin() const { 15 return Layout.block_begin() + Layout.Fragments[Num.get()]; 16 } 17 FunctionFragment::const_iterator FunctionFragment::end() const { 18 return Layout.block_begin() + Layout.Fragments[Num.get() + 1]; 19 } 20 BinaryBasicBlock *FunctionFragment::front() const { return *begin(); } 21 22 FunctionFragment FunctionLayout::addFragment() { 23 Fragments.emplace_back(Blocks.size()); 24 return getFragment(FragmentNum(Blocks.size() - 1)); 25 } 26 27 FunctionFragment FunctionLayout::getFragment(FragmentNum Num) const { 28 return FunctionFragment(Num, *this); 29 } 30 31 FunctionFragment 32 FunctionLayout::findFragment(const BinaryBasicBlock *BB) const { 33 return getFragment(BB->getFragmentNum()); 34 } 35 36 void FunctionLayout::addBasicBlock(BinaryBasicBlock *BB) { 37 BB->setLayoutIndex(Blocks.size()); 38 Blocks.emplace_back(BB); 39 ++Fragments.back(); 40 assert(Fragments.back() == Blocks.size()); 41 } 42 43 void FunctionLayout::insertBasicBlocks(BinaryBasicBlock *InsertAfter, 44 ArrayRef<BinaryBasicBlock *> NewBlocks) { 45 const block_iterator InsertBeforePos = 46 InsertAfter ? std::next(findBasicBlockPos(InsertAfter)) : Blocks.begin(); 47 Blocks.insert(InsertBeforePos, NewBlocks.begin(), NewBlocks.end()); 48 49 unsigned FragmentUpdateStart = 50 InsertAfter ? InsertAfter->getFragmentNum().get() + 1 : 1; 51 std::for_each( 52 Fragments.begin() + FragmentUpdateStart, Fragments.end(), 53 [&](unsigned &FragmentOffset) { FragmentOffset += NewBlocks.size(); }); 54 } 55 56 void FunctionLayout::eraseBasicBlocks( 57 const DenseSet<const BinaryBasicBlock *> ToErase) { 58 auto IsErased = [&](const BinaryBasicBlock *const BB) { 59 return ToErase.contains(BB); 60 }; 61 FragmentListType NewFragments; 62 NewFragments.emplace_back(0); 63 for (const FunctionFragment FF : fragments()) { 64 unsigned ErasedBlocks = count_if(FF, IsErased); 65 // Only add the fragment if it is non-empty after removing blocks. 66 unsigned NewFragment = NewFragments.back() + FF.size() - ErasedBlocks; 67 NewFragments.emplace_back(NewFragment); 68 } 69 llvm::erase_if(Blocks, IsErased); 70 Fragments = std::move(NewFragments); 71 72 // Remove empty fragments at the end 73 const_iterator EmptyTailBegin = 74 llvm::find_if_not(reverse(fragments()), [](const FunctionFragment &FF) { 75 return FF.empty(); 76 }).base(); 77 if (EmptyTailBegin != fragment_end()) { 78 // Add +1 for one-past-the-end entry 79 const FunctionFragment TailBegin = *EmptyTailBegin; 80 unsigned NewFragmentSize = TailBegin.getFragmentNum().get() + 1; 81 Fragments.resize(NewFragmentSize); 82 } 83 84 updateLayoutIndices(); 85 } 86 87 void FunctionLayout::updateLayoutIndices() const { 88 unsigned BlockIndex = 0; 89 for (const FunctionFragment FF : fragments()) { 90 for (BinaryBasicBlock *const BB : FF) { 91 BB->setLayoutIndex(BlockIndex++); 92 BB->setFragmentNum(FF.getFragmentNum()); 93 } 94 } 95 } 96 97 bool FunctionLayout::update(const ArrayRef<BinaryBasicBlock *> NewLayout) { 98 const bool EqualBlockOrder = llvm::equal(Blocks, NewLayout); 99 if (EqualBlockOrder) { 100 const bool EqualPartitioning = 101 llvm::all_of(fragments(), [](const FunctionFragment FF) { 102 return llvm::all_of(FF, [&](const BinaryBasicBlock *const BB) { 103 return FF.Num == BB->getFragmentNum(); 104 }); 105 }); 106 if (EqualPartitioning) 107 return false; 108 } 109 110 Blocks = BasicBlockListType(NewLayout.begin(), NewLayout.end()); 111 Fragments = {0, 0}; 112 113 // Generate fragments 114 for (const auto &BB : enumerate(Blocks)) { 115 unsigned FragmentNum = BB.value()->getFragmentNum().get(); 116 117 assert(FragmentNum >= fragment_size() - 1 && 118 "Blocks must be arranged such that fragments are monotonically " 119 "increasing."); 120 121 // Add empty fragments if necessary 122 for (unsigned I = fragment_size(); I <= FragmentNum; ++I) { 123 addFragment(); 124 Fragments[I] = BB.index(); 125 } 126 127 // Set the next fragment to point one past the current BB 128 Fragments[FragmentNum + 1] = BB.index() + 1; 129 } 130 131 return true; 132 } 133 134 void FunctionLayout::clear() { 135 Blocks = {}; 136 Fragments = {0, 0}; 137 } 138 139 BinaryBasicBlock *FunctionLayout::getBasicBlockAfter(const BinaryBasicBlock *BB, 140 bool IgnoreSplits) const { 141 const block_const_iterator BBPos = find(Blocks, BB); 142 if (BBPos == Blocks.end()) 143 return nullptr; 144 145 const block_const_iterator BlockAfter = std::next(BBPos); 146 if (BlockAfter == Blocks.end()) 147 return nullptr; 148 149 if (!IgnoreSplits) 150 if (BlockAfter == getFragment(BB->getFragmentNum()).end()) 151 return nullptr; 152 153 return *BlockAfter; 154 } 155 156 bool FunctionLayout::isSplit() const { 157 unsigned NonEmptyFragCount = llvm::count_if( 158 fragments(), [](const FunctionFragment &FF) { return !FF.empty(); }); 159 return NonEmptyFragCount >= 2; 160 } 161 162 uint64_t FunctionLayout::getEditDistance( 163 const ArrayRef<const BinaryBasicBlock *> OldBlockOrder) const { 164 return ComputeEditDistance<const BinaryBasicBlock *>(OldBlockOrder, Blocks); 165 } 166 167 FunctionLayout::block_const_iterator 168 FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) const { 169 return find(Blocks, BB); 170 } 171 172 FunctionLayout::block_iterator 173 FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) { 174 return find(Blocks, BB); 175 } 176