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 | |
16 | using namespace llvm; |
17 | using namespace bolt; |
18 | |
19 | FunctionFragment::FunctionFragment(FunctionLayout &Layout, |
20 | const FragmentNum Num) |
21 | : Layout(&Layout), Num(Num), StartIndex(Layout.block_size()) {} |
22 | |
23 | FunctionFragment::iterator FunctionFragment::begin() { |
24 | return iterator(Layout->block_begin() + StartIndex); |
25 | } |
26 | FunctionFragment::const_iterator FunctionFragment::begin() const { |
27 | return const_iterator(Layout->block_begin() + StartIndex); |
28 | } |
29 | FunctionFragment::iterator FunctionFragment::end() { |
30 | return iterator(Layout->block_begin() + StartIndex + Size); |
31 | } |
32 | FunctionFragment::const_iterator FunctionFragment::end() const { |
33 | return const_iterator(Layout->block_begin() + StartIndex + Size); |
34 | } |
35 | |
36 | BinaryBasicBlock *FunctionFragment::front() const { return *begin(); } |
37 | |
38 | BinaryBasicBlock *FunctionFragment::back() const { return *std::prev(x: end()); } |
39 | |
40 | FunctionLayout::FunctionLayout() { addFragment(); } |
41 | |
42 | FunctionLayout::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 | |
51 | FunctionLayout::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 | |
57 | FunctionLayout &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 | |
67 | FunctionLayout &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 | |
75 | FunctionLayout::~FunctionLayout() { |
76 | for (FunctionFragment *const F : Fragments) { |
77 | delete F; |
78 | } |
79 | } |
80 | |
81 | FunctionFragment &FunctionLayout::addFragment() { |
82 | FunctionFragment *const FF = |
83 | new FunctionFragment(*this, FragmentNum(Fragments.size())); |
84 | Fragments.emplace_back(Args: FF); |
85 | return *FF; |
86 | } |
87 | |
88 | FunctionFragment &FunctionLayout::getFragment(FragmentNum Num) { |
89 | return *Fragments[Num.get()]; |
90 | } |
91 | |
92 | const FunctionFragment &FunctionLayout::getFragment(FragmentNum Num) const { |
93 | return *Fragments[Num.get()]; |
94 | } |
95 | |
96 | const FunctionFragment & |
97 | FunctionLayout::findFragment(const BinaryBasicBlock *const BB) const { |
98 | return getFragment(Num: BB->getFragmentNum()); |
99 | } |
100 | |
101 | void FunctionLayout::addBasicBlock(BinaryBasicBlock *const BB) { |
102 | BB->setLayoutIndex(Blocks.size()); |
103 | Blocks.emplace_back(Args: BB); |
104 | Fragments.back()->Size++; |
105 | } |
106 | |
107 | void 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 | |
140 | void 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 | |
169 | void 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 | } |
178 | void FunctionLayout::updateLayoutIndices( |
179 | ArrayRef<BinaryBasicBlock *> Order) const { |
180 | for (auto [Index, BB] : llvm::enumerate(First&: Order)) |
181 | BB->setLayoutIndex(Index); |
182 | } |
183 | |
184 | bool 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 | |
214 | void 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 | |
226 | const BinaryBasicBlock * |
227 | FunctionLayout::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 | |
244 | bool 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 | |
250 | uint64_t FunctionLayout::getEditDistance( |
251 | const ArrayRef<const BinaryBasicBlock *> OldBlockOrder) const { |
252 | return ComputeEditDistance<const BinaryBasicBlock *>(FromArray: OldBlockOrder, ToArray: Blocks); |
253 | } |
254 | |
255 | FunctionLayout::block_const_iterator |
256 | FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) const { |
257 | return block_const_iterator(find(Range: Blocks, Val: BB)); |
258 | } |
259 | |
260 | FunctionLayout::block_iterator |
261 | FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) { |
262 | return find(Range&: Blocks, Val: BB); |
263 | } |
264 |
Definitions
- FunctionFragment
- begin
- begin
- end
- end
- front
- back
- FunctionLayout
- FunctionLayout
- FunctionLayout
- operator=
- operator=
- ~FunctionLayout
- addFragment
- getFragment
- getFragment
- findFragment
- addBasicBlock
- insertBasicBlocks
- eraseBasicBlocks
- updateLayoutIndices
- updateLayoutIndices
- update
- clear
- getBasicBlockAfter
- isSplit
- getEditDistance
- findBasicBlockPos
Improve your Profiling and Debugging skills
Find out more