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
size() const11 unsigned FunctionFragment::size() const { return end() - begin(); }
empty() const12 bool FunctionFragment::empty() const { return end() == begin(); }
begin() const13 FunctionFragment::const_iterator FunctionFragment::begin() const {
14 return Layout.block_begin() + Layout.Fragments[Num.get()];
15 }
end() const16 FunctionFragment::const_iterator FunctionFragment::end() const {
17 return Layout.block_begin() + Layout.Fragments[Num.get() + 1];
18 }
front() const19 BinaryBasicBlock *FunctionFragment::front() const { return *begin(); }
20
addFragment()21 FunctionFragment FunctionLayout::addFragment() {
22 Fragments.emplace_back(Blocks.size());
23 return back();
24 }
25
getFragment(FragmentNum Num) const26 FunctionFragment FunctionLayout::getFragment(FragmentNum Num) const {
27 return FunctionFragment(Num, *this);
28 }
29
30 FunctionFragment
findFragment(const BinaryBasicBlock * BB) const31 FunctionLayout::findFragment(const BinaryBasicBlock *BB) const {
32 return getFragment(BB->getFragmentNum());
33 }
34
addBasicBlock(BinaryBasicBlock * BB)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
insertBasicBlocks(BinaryBasicBlock * InsertAfter,ArrayRef<BinaryBasicBlock * > NewBlocks)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
eraseBasicBlocks(const DenseSet<const BinaryBasicBlock * > ToErase)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 Blocks.erase(std::remove_if(Blocks.begin(), Blocks.end(), IsErased),
75 Blocks.end());
76 Fragments = std::move(NewFragments);
77 }
78
updateLayoutIndices() const79 void FunctionLayout::updateLayoutIndices() const {
80 unsigned BlockIndex = 0;
81 for (const FunctionFragment F : *this) {
82 for (BinaryBasicBlock *const BB : F)
83 BB->setLayoutIndex(BlockIndex++);
84 }
85 }
86
update(const ArrayRef<BinaryBasicBlock * > NewLayout)87 void FunctionLayout::update(const ArrayRef<BinaryBasicBlock *> NewLayout) {
88 PreviousBlocks = std::move(Blocks);
89 PreviousFragments = std::move(Fragments);
90
91 Blocks.clear();
92 Fragments = {0};
93
94 if (NewLayout.empty())
95 return;
96
97 copy(NewLayout, std::back_inserter(Blocks));
98
99 // Generate fragments
100 for (const auto &BB : enumerate(Blocks)) {
101 unsigned FragmentNum = BB.value()->getFragmentNum().get();
102
103 assert(FragmentNum + 1 >= size() &&
104 "Blocks must be arranged such that fragments are monotonically "
105 "increasing.");
106
107 // Add empty fragments if necessary
108 for (unsigned I = size(); I <= FragmentNum; ++I) {
109 addFragment();
110 Fragments[I] = BB.index();
111 }
112
113 // Set the next fragment to point one past the current BB
114 Fragments[FragmentNum + 1] = BB.index() + 1;
115 }
116
117 if (PreviousBlocks == Blocks && PreviousFragments == Fragments) {
118 // If new layout is the same as previous layout, clear previous layout so
119 // hasLayoutChanged() returns false.
120 PreviousBlocks = {};
121 PreviousFragments = {};
122 }
123 }
124
clear()125 void FunctionLayout::clear() {
126 Blocks = {};
127 Fragments = {0};
128 PreviousBlocks = {};
129 PreviousFragments = {0};
130 }
131
getBasicBlockAfter(const BinaryBasicBlock * BB,bool IgnoreSplits) const132 BinaryBasicBlock *FunctionLayout::getBasicBlockAfter(const BinaryBasicBlock *BB,
133 bool IgnoreSplits) const {
134 const block_const_iterator BBPos = find(Blocks, BB);
135 if (BBPos == Blocks.end())
136 return nullptr;
137
138 const block_const_iterator BlockAfter = std::next(BBPos);
139 if (BlockAfter == Blocks.end())
140 return nullptr;
141
142 if (!IgnoreSplits)
143 if (BlockAfter == getFragment(BB->getFragmentNum()).end())
144 return nullptr;
145
146 return *BlockAfter;
147 }
148
isSplit() const149 bool FunctionLayout::isSplit() const {
150 unsigned NonEmptyFragCount = llvm::count_if(
151 *this, [](const FunctionFragment &F) { return !F.empty(); });
152 return NonEmptyFragCount >= 2;
153 }
154
getEditDistance() const155 uint64_t FunctionLayout::getEditDistance() const {
156 return ComputeEditDistance<BinaryBasicBlock *>(PreviousBlocks, Blocks);
157 }
158
159 FunctionLayout::block_const_iterator
findBasicBlockPos(const BinaryBasicBlock * BB) const160 FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) const {
161 return find(Blocks, BB);
162 }
163
164 FunctionLayout::block_iterator
findBasicBlockPos(const BinaryBasicBlock * BB)165 FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) {
166 return find(Blocks, BB);
167 }
168