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

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