1 | //===- bolt/Core/FunctionLayout.h - 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 | // This file contains the declaration of the FunctionLayout class. The layout of |
10 | // a function is the order of basic blocks, in which we will arrange them in the |
11 | // new binary. Normally, when not optimizing for code layout, the blocks of a |
12 | // function are contiguous. However, we can split the layout into multiple |
13 | // fragments. The blocks within a fragment are contiguous, but the fragments |
14 | // itself are disjoint. Fragments could be used to enhance code layout, e.g. to |
15 | // separate the blocks into hot and cold sections. |
16 | // |
17 | //===----------------------------------------------------------------------===// |
18 | |
19 | #ifndef BOLT_CORE_FUNCTION_LAYOUT_H |
20 | #define BOLT_CORE_FUNCTION_LAYOUT_H |
21 | |
22 | #include "llvm/ADT/ArrayRef.h" |
23 | #include "llvm/ADT/DenseSet.h" |
24 | #include "llvm/ADT/SmallVector.h" |
25 | #include "llvm/ADT/iterator.h" |
26 | #include "llvm/ADT/iterator_range.h" |
27 | #include <iterator> |
28 | |
29 | namespace llvm { |
30 | namespace bolt { |
31 | |
32 | class BinaryFunction; |
33 | class BinaryBasicBlock; |
34 | class FunctionLayout; |
35 | |
36 | class FragmentNum { |
37 | unsigned Value{0}; |
38 | |
39 | public: |
40 | constexpr FragmentNum() = default; |
41 | constexpr explicit FragmentNum(unsigned Value) : Value(Value) {} |
42 | constexpr unsigned get() const { return Value; } |
43 | |
44 | constexpr bool operator==(const FragmentNum Other) const { |
45 | return Value == Other.Value; |
46 | } |
47 | constexpr bool operator!=(const FragmentNum Other) const { |
48 | return Value != Other.Value; |
49 | } |
50 | constexpr bool operator<(const FragmentNum Other) const { |
51 | return Value < Other.Value; |
52 | } |
53 | constexpr bool operator<=(const FragmentNum Other) const { |
54 | return Value <= Other.Value; |
55 | } |
56 | constexpr bool operator>=(const FragmentNum Other) const { |
57 | return Value >= Other.Value; |
58 | } |
59 | constexpr bool operator>(const FragmentNum Other) const { |
60 | return Value > Other.Value; |
61 | } |
62 | |
63 | static constexpr FragmentNum main() { return FragmentNum(0); } |
64 | static constexpr FragmentNum cold() { return FragmentNum(1); } |
65 | static constexpr FragmentNum warm() { return FragmentNum(2); } |
66 | }; |
67 | |
68 | /// A freestanding subset of contiguous blocks of a function. |
69 | class FunctionFragment { |
70 | using BasicBlockListType = SmallVector<BinaryBasicBlock *, 0>; |
71 | using FragmentListType = SmallVector<unsigned, 0>; |
72 | |
73 | public: |
74 | using iterator = BasicBlockListType::iterator; |
75 | using const_iterator = BasicBlockListType::const_iterator; |
76 | |
77 | private: |
78 | FunctionLayout *Layout; |
79 | FragmentNum Num; |
80 | unsigned StartIndex; |
81 | unsigned Size = 0; |
82 | |
83 | /// Output address for the fragment. |
84 | uint64_t Address = 0; |
85 | |
86 | /// The address for the code for this fragment in codegen memory. Used for |
87 | /// functions that are emitted in a dedicated section with a fixed address, |
88 | /// e.g. for functions that are overwritten in-place. |
89 | uint64_t ImageAddress = 0; |
90 | |
91 | /// The size of the code in memory. |
92 | uint64_t ImageSize = 0; |
93 | |
94 | /// Offset in the file. |
95 | uint64_t FileOffset = 0; |
96 | |
97 | FunctionFragment(FunctionLayout &Layout, FragmentNum Num); |
98 | FunctionFragment(const FunctionFragment &) = default; |
99 | FunctionFragment(FunctionFragment &&) = default; |
100 | FunctionFragment &operator=(const FunctionFragment &) = default; |
101 | FunctionFragment &operator=(FunctionFragment &&) = default; |
102 | ~FunctionFragment() = default; |
103 | |
104 | public: |
105 | FragmentNum getFragmentNum() const { return Num; } |
106 | bool isMainFragment() const { |
107 | return getFragmentNum() == FragmentNum::main(); |
108 | } |
109 | bool isSplitFragment() const { return !isMainFragment(); } |
110 | |
111 | uint64_t getAddress() const { return Address; } |
112 | void setAddress(uint64_t Value) { Address = Value; } |
113 | uint64_t getImageAddress() const { return ImageAddress; } |
114 | void setImageAddress(uint64_t Address) { ImageAddress = Address; } |
115 | uint64_t getImageSize() const { return ImageSize; } |
116 | void setImageSize(uint64_t Size) { ImageSize = Size; } |
117 | uint64_t getFileOffset() const { return FileOffset; } |
118 | void setFileOffset(uint64_t Offset) { FileOffset = Offset; } |
119 | |
120 | unsigned size() const { return Size; }; |
121 | bool empty() const { return size() == 0; }; |
122 | iterator begin(); |
123 | const_iterator begin() const; |
124 | iterator end(); |
125 | const_iterator end() const; |
126 | const BinaryBasicBlock *front() const; |
127 | |
128 | friend class FunctionLayout; |
129 | }; |
130 | |
131 | /// The function layout represents the fragments we split a function into and |
132 | /// the order of basic blocks within each fragment. |
133 | /// |
134 | /// Internally, the function layout stores blocks across fragments contiguously. |
135 | /// This is necessary to retain compatibility with existing code and tests that |
136 | /// iterate over all blocks of the layout and depend on that order. When |
137 | /// writing new code, avoid iterating using FunctionLayout::blocks() by |
138 | /// iterating either over fragments or over BinaryFunction::begin()..end(). |
139 | class FunctionLayout { |
140 | private: |
141 | using FragmentListType = SmallVector<FunctionFragment *, 0>; |
142 | using BasicBlockListType = SmallVector<BinaryBasicBlock *, 0>; |
143 | |
144 | public: |
145 | using fragment_iterator = pointee_iterator<FragmentListType::const_iterator>; |
146 | using fragment_const_iterator = |
147 | pointee_iterator<FragmentListType::const_iterator, |
148 | const FunctionFragment>; |
149 | using block_iterator = BasicBlockListType::iterator; |
150 | using block_const_iterator = BasicBlockListType::const_iterator; |
151 | using block_reverse_iterator = std::reverse_iterator<block_iterator>; |
152 | using block_const_reverse_iterator = |
153 | std::reverse_iterator<block_const_iterator>; |
154 | |
155 | private: |
156 | FragmentListType Fragments; |
157 | BasicBlockListType Blocks; |
158 | |
159 | public: |
160 | FunctionLayout(); |
161 | FunctionLayout(const FunctionLayout &Other); |
162 | FunctionLayout(FunctionLayout &&Other); |
163 | FunctionLayout &operator=(const FunctionLayout &Other); |
164 | FunctionLayout &operator=(FunctionLayout &&Other); |
165 | ~FunctionLayout(); |
166 | |
167 | /// Add an empty fragment. |
168 | FunctionFragment &addFragment(); |
169 | |
170 | /// Return the fragment identified by Num. |
171 | FunctionFragment &getFragment(FragmentNum Num); |
172 | |
173 | /// Return the fragment identified by Num. |
174 | const FunctionFragment &getFragment(FragmentNum Num) const; |
175 | |
176 | /// Get the fragment that contains all entry blocks and other blocks that |
177 | /// cannot be split. |
178 | FunctionFragment &getMainFragment() { |
179 | return getFragment(Num: FragmentNum::main()); |
180 | } |
181 | |
182 | /// Get the fragment that contains all entry blocks and other blocks that |
183 | /// cannot be split. |
184 | const FunctionFragment &getMainFragment() const { |
185 | return getFragment(Num: FragmentNum::main()); |
186 | } |
187 | |
188 | /// Get the fragment that contains all entry blocks and other blocks that |
189 | /// cannot be split. |
190 | iterator_range<fragment_iterator> getSplitFragments() { |
191 | return {++fragment_begin(), fragment_end()}; |
192 | } |
193 | |
194 | /// Get the fragment that contains all entry blocks and other blocks that |
195 | /// cannot be split. |
196 | iterator_range<fragment_const_iterator> getSplitFragments() const { |
197 | return {++fragment_begin(), fragment_end()}; |
198 | } |
199 | |
200 | /// Find the fragment that contains BB. |
201 | const FunctionFragment &findFragment(const BinaryBasicBlock *BB) const; |
202 | |
203 | /// Add BB to the end of the last fragment. |
204 | void addBasicBlock(BinaryBasicBlock *BB); |
205 | |
206 | /// Insert range of basic blocks after InsertAfter. If InsertAfter is nullptr, |
207 | /// the blocks will be inserted at the start of the function. |
208 | void insertBasicBlocks(const BinaryBasicBlock *InsertAfter, |
209 | ArrayRef<BinaryBasicBlock *> NewBlocks); |
210 | |
211 | /// Erase all blocks from the layout that are in ToErase. If this method |
212 | /// erases all blocks of a fragment, it will be removed as well. |
213 | void eraseBasicBlocks(const DenseSet<const BinaryBasicBlock *> ToErase); |
214 | |
215 | /// Make sure fragments' and basic blocks' indices match the current layout. |
216 | void updateLayoutIndices(); |
217 | |
218 | /// Replace the current layout with NewLayout. Uses the block's |
219 | /// self-identifying fragment number to assign blocks to infer function |
220 | /// fragments. Returns `true` if the new layout is different from the current |
221 | /// layout. |
222 | bool update(ArrayRef<BinaryBasicBlock *> NewLayout); |
223 | |
224 | /// Clear layout releasing memory. |
225 | void clear(); |
226 | |
227 | BinaryBasicBlock *getBlock(unsigned Index) { return Blocks[Index]; } |
228 | |
229 | const BinaryBasicBlock *getBlock(unsigned Index) const { |
230 | return Blocks[Index]; |
231 | } |
232 | |
233 | /// Returns the basic block after the given basic block in the layout or |
234 | /// nullptr if the last basic block is given. |
235 | BinaryBasicBlock *getBasicBlockAfter(const BinaryBasicBlock *const BB, |
236 | const bool IgnoreSplits = true) { |
237 | return const_cast<BinaryBasicBlock *>( |
238 | static_cast<const FunctionLayout &>(*this).getBasicBlockAfter( |
239 | BB, IgnoreSplits)); |
240 | } |
241 | |
242 | /// Returns the basic block after the given basic block in the layout or |
243 | /// nullptr if the last basic block is given. |
244 | const BinaryBasicBlock *getBasicBlockAfter(const BinaryBasicBlock *BB, |
245 | bool IgnoreSplits = true) const; |
246 | |
247 | /// True if the layout contains at least two non-empty fragments. |
248 | bool isSplit() const; |
249 | |
250 | /// Get the edit distance of the new layout with respect to the previous |
251 | /// layout after basic block reordering. |
252 | uint64_t |
253 | getEditDistance(ArrayRef<const BinaryBasicBlock *> OldBlockOrder) const; |
254 | |
255 | /// True if the function is split into at most 2 fragments. Mostly used for |
256 | /// checking whether a function can be processed in places that do not support |
257 | /// multiple fragments yet. |
258 | bool isHotColdSplit() const { return fragment_size() <= 2; } |
259 | |
260 | size_t fragment_size() const { |
261 | assert(Fragments.size() >= 1 && |
262 | "Layout should have at least one fragment." ); |
263 | return Fragments.size(); |
264 | } |
265 | bool fragment_empty() const { return fragment_size() == 0; } |
266 | |
267 | fragment_iterator fragment_begin() { return Fragments.begin(); } |
268 | fragment_const_iterator fragment_begin() const { return Fragments.begin(); } |
269 | fragment_iterator fragment_end() { return Fragments.end(); } |
270 | fragment_const_iterator fragment_end() const { return Fragments.end(); } |
271 | iterator_range<fragment_iterator> fragments() { |
272 | return {fragment_begin(), fragment_end()}; |
273 | } |
274 | iterator_range<fragment_const_iterator> fragments() const { |
275 | return {fragment_begin(), fragment_end()}; |
276 | } |
277 | |
278 | size_t block_size() const { return Blocks.size(); } |
279 | bool block_empty() const { return Blocks.empty(); } |
280 | |
281 | /// Required to return non-const qualified `BinaryBasicBlock *` for graph |
282 | /// traits. |
283 | BinaryBasicBlock *block_front() const { return Blocks.front(); } |
284 | const BinaryBasicBlock *block_back() const { return Blocks.back(); } |
285 | |
286 | block_iterator block_begin() { return Blocks.begin(); } |
287 | block_const_iterator block_begin() const { |
288 | return block_const_iterator(Blocks.begin()); |
289 | } |
290 | block_iterator block_end() { return Blocks.end(); } |
291 | block_const_iterator block_end() const { |
292 | return block_const_iterator(Blocks.end()); |
293 | } |
294 | iterator_range<block_iterator> blocks() { |
295 | return {block_begin(), block_end()}; |
296 | } |
297 | iterator_range<block_const_iterator> blocks() const { |
298 | return {block_begin(), block_end()}; |
299 | } |
300 | block_reverse_iterator block_rbegin() { |
301 | return block_reverse_iterator(Blocks.rbegin()); |
302 | } |
303 | block_const_reverse_iterator block_rbegin() const { |
304 | return block_const_reverse_iterator( |
305 | std::make_reverse_iterator(i: block_end())); |
306 | } |
307 | block_reverse_iterator block_rend() { |
308 | return block_reverse_iterator(Blocks.rend()); |
309 | } |
310 | block_const_reverse_iterator block_rend() const { |
311 | return block_const_reverse_iterator( |
312 | std::make_reverse_iterator(i: block_begin())); |
313 | } |
314 | iterator_range<block_const_reverse_iterator> rblocks() const { |
315 | return {block_rbegin(), block_rend()}; |
316 | } |
317 | |
318 | private: |
319 | block_const_iterator findBasicBlockPos(const BinaryBasicBlock *BB) const; |
320 | block_iterator findBasicBlockPos(const BinaryBasicBlock *BB); |
321 | |
322 | friend class FunctionFragment; |
323 | }; |
324 | |
325 | } // namespace bolt |
326 | } // namespace llvm |
327 | |
328 | #endif |
329 | |