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