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 #include <iterator> 9 #include <memory> 10 11 using namespace llvm; 12 using namespace bolt; 13 14 FunctionFragment::FunctionFragment(FunctionLayout &Layout, 15 const FragmentNum Num) 16 : Layout(&Layout), Num(Num), StartIndex(Layout.block_size()) {} 17 18 FunctionFragment::iterator FunctionFragment::begin() { 19 return iterator(Layout->block_begin() + StartIndex); 20 } 21 FunctionFragment::const_iterator FunctionFragment::begin() const { 22 return const_iterator(Layout->block_begin() + StartIndex); 23 } 24 FunctionFragment::iterator FunctionFragment::end() { 25 return iterator(Layout->block_begin() + StartIndex + Size); 26 } 27 FunctionFragment::const_iterator FunctionFragment::end() const { 28 return const_iterator(Layout->block_begin() + StartIndex + Size); 29 } 30 31 const BinaryBasicBlock *FunctionFragment::front() const { return *begin(); } 32 33 FunctionLayout::FunctionLayout() { addFragment(); } 34 35 FunctionLayout::FunctionLayout(const FunctionLayout &Other) 36 : Blocks(Other.Blocks) { 37 for (FunctionFragment *const FF : Other.Fragments) { 38 auto *Copy = new FunctionFragment(*FF); 39 Copy->Layout = this; 40 Fragments.emplace_back(Copy); 41 } 42 } 43 44 FunctionLayout::FunctionLayout(FunctionLayout &&Other) 45 : Fragments(std::move(Other.Fragments)), Blocks(std::move(Other.Blocks)) { 46 for (FunctionFragment *const F : Fragments) 47 F->Layout = this; 48 } 49 50 FunctionLayout &FunctionLayout::operator=(const FunctionLayout &Other) { 51 Blocks = Other.Blocks; 52 for (FunctionFragment *const FF : Other.Fragments) { 53 auto *const Copy = new FunctionFragment(*FF); 54 Copy->Layout = this; 55 Fragments.emplace_back(Copy); 56 } 57 return *this; 58 } 59 60 FunctionLayout &FunctionLayout::operator=(FunctionLayout &&Other) { 61 Fragments = std::move(Other.Fragments); 62 Blocks = std::move(Other.Blocks); 63 for (FunctionFragment *const FF : Fragments) 64 FF->Layout = this; 65 return *this; 66 } 67 68 FunctionLayout::~FunctionLayout() { 69 for (FunctionFragment *const F : Fragments) { 70 delete F; 71 } 72 } 73 74 FunctionFragment &FunctionLayout::addFragment() { 75 FunctionFragment *const FF = 76 new FunctionFragment(*this, FragmentNum(Fragments.size())); 77 Fragments.emplace_back(FF); 78 return *FF; 79 } 80 81 FunctionFragment &FunctionLayout::getFragment(FragmentNum Num) { 82 return *Fragments[Num.get()]; 83 } 84 85 const FunctionFragment &FunctionLayout::getFragment(FragmentNum Num) const { 86 return *Fragments[Num.get()]; 87 } 88 89 const FunctionFragment & 90 FunctionLayout::findFragment(const BinaryBasicBlock *const BB) const { 91 return getFragment(BB->getFragmentNum()); 92 } 93 94 void FunctionLayout::addBasicBlock(BinaryBasicBlock *const BB) { 95 BB->setLayoutIndex(Blocks.size()); 96 Blocks.emplace_back(BB); 97 Fragments.back()->Size++; 98 } 99 100 void FunctionLayout::insertBasicBlocks( 101 const BinaryBasicBlock *const InsertAfter, 102 const ArrayRef<BinaryBasicBlock *> NewBlocks) { 103 block_iterator InsertBeforePos = Blocks.begin(); 104 FragmentNum InsertFragmentNum = FragmentNum::main(); 105 unsigned LayoutIndex = 0; 106 107 if (InsertAfter) { 108 InsertBeforePos = std::next(findBasicBlockPos(InsertAfter)); 109 InsertFragmentNum = InsertAfter->getFragmentNum(); 110 LayoutIndex = InsertAfter->getLayoutIndex(); 111 } 112 113 llvm::copy(NewBlocks, std::inserter(Blocks, InsertBeforePos)); 114 115 for (BinaryBasicBlock *const BB : NewBlocks) { 116 BB->setFragmentNum(InsertFragmentNum); 117 BB->setLayoutIndex(LayoutIndex++); 118 } 119 120 const fragment_iterator InsertFragment = 121 fragment_begin() + InsertFragmentNum.get(); 122 InsertFragment->Size += NewBlocks.size(); 123 124 const fragment_iterator TailBegin = std::next(InsertFragment); 125 auto const UpdateFragment = [&](FunctionFragment &FF) { 126 FF.StartIndex += NewBlocks.size(); 127 for (BinaryBasicBlock *const BB : FF) 128 BB->setLayoutIndex(LayoutIndex++); 129 }; 130 std::for_each(TailBegin, fragment_end(), UpdateFragment); 131 } 132 133 void FunctionLayout::eraseBasicBlocks( 134 const DenseSet<const BinaryBasicBlock *> ToErase) { 135 const auto IsErased = [&](const BinaryBasicBlock *const BB) { 136 return ToErase.contains(BB); 137 }; 138 139 unsigned TotalErased = 0; 140 for (FunctionFragment &FF : fragments()) { 141 unsigned Erased = count_if(FF, IsErased); 142 FF.Size -= Erased; 143 FF.StartIndex -= TotalErased; 144 TotalErased += Erased; 145 } 146 llvm::erase_if(Blocks, IsErased); 147 148 // Remove empty fragments at the end 149 const auto IsEmpty = [](const FunctionFragment *const FF) { 150 return FF->empty(); 151 }; 152 const FragmentListType::iterator EmptyTailBegin = 153 llvm::find_if_not(reverse(Fragments), IsEmpty).base(); 154 std::for_each(EmptyTailBegin, Fragments.end(), 155 [](FunctionFragment *const FF) { delete FF; }); 156 Fragments.erase(EmptyTailBegin, Fragments.end()); 157 158 updateLayoutIndices(); 159 } 160 161 void FunctionLayout::updateLayoutIndices() { 162 unsigned BlockIndex = 0; 163 for (FunctionFragment &FF : fragments()) { 164 for (BinaryBasicBlock *const BB : FF) { 165 BB->setLayoutIndex(BlockIndex++); 166 BB->setFragmentNum(FF.getFragmentNum()); 167 } 168 } 169 } 170 171 bool FunctionLayout::update(const ArrayRef<BinaryBasicBlock *> NewLayout) { 172 const bool EqualBlockOrder = llvm::equal(Blocks, NewLayout); 173 if (EqualBlockOrder) { 174 const bool EqualPartitioning = 175 llvm::all_of(fragments(), [](const FunctionFragment &FF) { 176 return llvm::all_of(FF, [&](const BinaryBasicBlock *const BB) { 177 return FF.Num == BB->getFragmentNum(); 178 }); 179 }); 180 if (EqualPartitioning) 181 return false; 182 } 183 184 clear(); 185 186 // Generate fragments 187 for (BinaryBasicBlock *const BB : NewLayout) { 188 FragmentNum Num = BB->getFragmentNum(); 189 190 assert(Num >= Fragments.back()->getFragmentNum() && 191 "Blocks must be arranged such that fragments are monotonically " 192 "increasing."); 193 194 // Add empty fragments if necessary 195 while (Fragments.back()->getFragmentNum() < Num) 196 addFragment(); 197 198 // Set the next fragment to point one past the current BB 199 addBasicBlock(BB); 200 } 201 202 return true; 203 } 204 205 void FunctionLayout::clear() { 206 Blocks = BasicBlockListType(); 207 for (FunctionFragment *const FF : Fragments) 208 delete FF; 209 Fragments = FragmentListType(); 210 addFragment(); 211 } 212 213 const BinaryBasicBlock * 214 FunctionLayout::getBasicBlockAfter(const BinaryBasicBlock *BB, 215 bool IgnoreSplits) const { 216 const block_const_iterator BBPos = find(blocks(), BB); 217 if (BBPos == block_end()) 218 return nullptr; 219 220 const block_const_iterator BlockAfter = std::next(BBPos); 221 if (BlockAfter == block_end()) 222 return nullptr; 223 224 if (!IgnoreSplits) 225 if (BlockAfter == getFragment(BB->getFragmentNum()).end()) 226 return nullptr; 227 228 return *BlockAfter; 229 } 230 231 bool FunctionLayout::isSplit() const { 232 const unsigned NonEmptyFragCount = llvm::count_if( 233 fragments(), [](const FunctionFragment &FF) { return !FF.empty(); }); 234 return NonEmptyFragCount >= 2; 235 } 236 237 uint64_t FunctionLayout::getEditDistance( 238 const ArrayRef<const BinaryBasicBlock *> OldBlockOrder) const { 239 return ComputeEditDistance<const BinaryBasicBlock *>(OldBlockOrder, Blocks); 240 } 241 242 FunctionLayout::block_const_iterator 243 FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) const { 244 return block_const_iterator(find(Blocks, BB)); 245 } 246 247 FunctionLayout::block_iterator 248 FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) { 249 return find(Blocks, BB); 250 } 251