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