1//===- bolt/Core/FunctionLayout.cpp - Fragmented Function Layout -*- C++ -*-==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "bolt/Core/FunctionLayout.h"
10#include "bolt/Core/BinaryBasicBlock.h"
11#include "llvm/ADT/STLExtras.h"
12#include "llvm/ADT/edit_distance.h"
13#include <algorithm>
14#include <iterator>
15
16using namespace llvm;
17using namespace bolt;
18
19FunctionFragment::FunctionFragment(FunctionLayout &Layout,
20 const FragmentNum Num)
21 : Layout(&Layout), Num(Num), StartIndex(Layout.block_size()) {}
22
23FunctionFragment::iterator FunctionFragment::begin() {
24 return iterator(Layout->block_begin() + StartIndex);
25}
26FunctionFragment::const_iterator FunctionFragment::begin() const {
27 return const_iterator(Layout->block_begin() + StartIndex);
28}
29FunctionFragment::iterator FunctionFragment::end() {
30 return iterator(Layout->block_begin() + StartIndex + Size);
31}
32FunctionFragment::const_iterator FunctionFragment::end() const {
33 return const_iterator(Layout->block_begin() + StartIndex + Size);
34}
35
36const BinaryBasicBlock *FunctionFragment::front() const { return *begin(); }
37
38FunctionLayout::FunctionLayout() { addFragment(); }
39
40FunctionLayout::FunctionLayout(const FunctionLayout &Other)
41 : Blocks(Other.Blocks) {
42 for (FunctionFragment *const FF : Other.Fragments) {
43 auto *Copy = new FunctionFragment(*FF);
44 Copy->Layout = this;
45 Fragments.emplace_back(Args&: Copy);
46 }
47}
48
49FunctionLayout::FunctionLayout(FunctionLayout &&Other)
50 : Fragments(std::move(Other.Fragments)), Blocks(std::move(Other.Blocks)) {
51 for (FunctionFragment *const F : Fragments)
52 F->Layout = this;
53}
54
55FunctionLayout &FunctionLayout::operator=(const FunctionLayout &Other) {
56 Blocks = Other.Blocks;
57 for (FunctionFragment *const FF : Other.Fragments) {
58 auto *const Copy = new FunctionFragment(*FF);
59 Copy->Layout = this;
60 Fragments.emplace_back(Args: Copy);
61 }
62 return *this;
63}
64
65FunctionLayout &FunctionLayout::operator=(FunctionLayout &&Other) {
66 Fragments = std::move(Other.Fragments);
67 Blocks = std::move(Other.Blocks);
68 for (FunctionFragment *const FF : Fragments)
69 FF->Layout = this;
70 return *this;
71}
72
73FunctionLayout::~FunctionLayout() {
74 for (FunctionFragment *const F : Fragments) {
75 delete F;
76 }
77}
78
79FunctionFragment &FunctionLayout::addFragment() {
80 FunctionFragment *const FF =
81 new FunctionFragment(*this, FragmentNum(Fragments.size()));
82 Fragments.emplace_back(Args: FF);
83 return *FF;
84}
85
86FunctionFragment &FunctionLayout::getFragment(FragmentNum Num) {
87 return *Fragments[Num.get()];
88}
89
90const FunctionFragment &FunctionLayout::getFragment(FragmentNum Num) const {
91 return *Fragments[Num.get()];
92}
93
94const FunctionFragment &
95FunctionLayout::findFragment(const BinaryBasicBlock *const BB) const {
96 return getFragment(Num: BB->getFragmentNum());
97}
98
99void FunctionLayout::addBasicBlock(BinaryBasicBlock *const BB) {
100 BB->setLayoutIndex(Blocks.size());
101 Blocks.emplace_back(Args: BB);
102 Fragments.back()->Size++;
103}
104
105void FunctionLayout::insertBasicBlocks(
106 const BinaryBasicBlock *const InsertAfter,
107 const ArrayRef<BinaryBasicBlock *> NewBlocks) {
108 block_iterator InsertBeforePos = Blocks.begin();
109 FragmentNum InsertFragmentNum = FragmentNum::main();
110 unsigned LayoutIndex = 0;
111
112 if (InsertAfter) {
113 InsertBeforePos = std::next(x: findBasicBlockPos(BB: InsertAfter));
114 InsertFragmentNum = InsertAfter->getFragmentNum();
115 LayoutIndex = InsertAfter->getLayoutIndex();
116 }
117
118 llvm::copy(Range: NewBlocks, Out: std::inserter(x&: Blocks, i: InsertBeforePos));
119
120 for (BinaryBasicBlock *const BB : NewBlocks) {
121 BB->setFragmentNum(InsertFragmentNum);
122 BB->setLayoutIndex(LayoutIndex++);
123 }
124
125 const fragment_iterator InsertFragment =
126 fragment_begin() + InsertFragmentNum.get();
127 InsertFragment->Size += NewBlocks.size();
128
129 const fragment_iterator TailBegin = std::next(x: InsertFragment);
130 auto const UpdateFragment = [&](FunctionFragment &FF) {
131 FF.StartIndex += NewBlocks.size();
132 for (BinaryBasicBlock *const BB : FF)
133 BB->setLayoutIndex(LayoutIndex++);
134 };
135 std::for_each(first: TailBegin, last: fragment_end(), f: UpdateFragment);
136}
137
138void FunctionLayout::eraseBasicBlocks(
139 const DenseSet<const BinaryBasicBlock *> ToErase) {
140 const auto IsErased = [&](const BinaryBasicBlock *const BB) {
141 return ToErase.contains(V: BB);
142 };
143
144 unsigned TotalErased = 0;
145 for (FunctionFragment &FF : fragments()) {
146 unsigned Erased = count_if(Range&: FF, P: IsErased);
147 FF.Size -= Erased;
148 FF.StartIndex -= TotalErased;
149 TotalErased += Erased;
150 }
151 llvm::erase_if(C&: Blocks, P: IsErased);
152
153 // Remove empty fragments at the end
154 const auto IsEmpty = [](const FunctionFragment *const FF) {
155 return FF->empty();
156 };
157 const FragmentListType::iterator EmptyTailBegin =
158 llvm::find_if_not(Range: reverse(C&: Fragments), P: IsEmpty).base();
159 for (FunctionFragment *const FF :
160 llvm::make_range(x: EmptyTailBegin, y: Fragments.end()))
161 delete FF;
162 Fragments.erase(CS: EmptyTailBegin, CE: Fragments.end());
163
164 updateLayoutIndices();
165}
166
167void FunctionLayout::updateLayoutIndices() {
168 unsigned BlockIndex = 0;
169 for (FunctionFragment &FF : fragments()) {
170 for (BinaryBasicBlock *const BB : FF) {
171 BB->setLayoutIndex(BlockIndex++);
172 BB->setFragmentNum(FF.getFragmentNum());
173 }
174 }
175}
176
177bool FunctionLayout::update(const ArrayRef<BinaryBasicBlock *> NewLayout) {
178 const bool EqualBlockOrder = llvm::equal(LRange&: Blocks, RRange: NewLayout);
179 if (EqualBlockOrder) {
180 const bool EqualPartitioning =
181 llvm::all_of(Range: fragments(), P: [](const FunctionFragment &FF) {
182 return llvm::all_of(Range: FF, P: [&](const BinaryBasicBlock *const BB) {
183 return FF.Num == BB->getFragmentNum();
184 });
185 });
186 if (EqualPartitioning)
187 return false;
188 }
189
190 clear();
191
192 // Generate fragments
193 for (BinaryBasicBlock *const BB : NewLayout) {
194 FragmentNum Num = BB->getFragmentNum();
195
196 // Add empty fragments if necessary
197 while (Fragments.back()->getFragmentNum() < Num)
198 addFragment();
199
200 // Set the next fragment to point one past the current BB
201 addBasicBlock(BB);
202 }
203
204 return true;
205}
206
207void FunctionLayout::clear() {
208 Blocks = BasicBlockListType();
209 // If the binary does not have relocations and is not split, the function will
210 // be written to the output stream at its original file offset (see
211 // `RewriteInstance::rewriteFile`). Hence, when the layout is cleared, retain
212 // the main fragment, so that this information is not lost.
213 for (FunctionFragment *const FF : llvm::drop_begin(RangeOrContainer&: Fragments))
214 delete FF;
215 Fragments = FragmentListType{Fragments.front()};
216 getMainFragment().Size = 0;
217}
218
219const BinaryBasicBlock *
220FunctionLayout::getBasicBlockAfter(const BinaryBasicBlock *BB,
221 bool IgnoreSplits) const {
222 const block_const_iterator BBPos = find(Range: blocks(), Val: BB);
223 if (BBPos == block_end())
224 return nullptr;
225
226 const block_const_iterator BlockAfter = std::next(x: BBPos);
227 if (BlockAfter == block_end())
228 return nullptr;
229
230 if (!IgnoreSplits)
231 if (BlockAfter == getFragment(Num: BB->getFragmentNum()).end())
232 return nullptr;
233
234 return *BlockAfter;
235}
236
237bool FunctionLayout::isSplit() const {
238 const unsigned NonEmptyFragCount = llvm::count_if(
239 Range: fragments(), P: [](const FunctionFragment &FF) { return !FF.empty(); });
240 return NonEmptyFragCount >= 2;
241}
242
243uint64_t FunctionLayout::getEditDistance(
244 const ArrayRef<const BinaryBasicBlock *> OldBlockOrder) const {
245 return ComputeEditDistance<const BinaryBasicBlock *>(FromArray: OldBlockOrder, ToArray: Blocks);
246}
247
248FunctionLayout::block_const_iterator
249FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) const {
250 return block_const_iterator(find(Range: Blocks, Val: BB));
251}
252
253FunctionLayout::block_iterator
254FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) {
255 return find(Range&: Blocks, Val: BB);
256}
257

source code of bolt/lib/Core/FunctionLayout.cpp