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
29namespace llvm {
30namespace bolt {
31
32class BinaryFunction;
33class BinaryBasicBlock;
34class FunctionLayout;
35
36class FragmentNum {
37 unsigned Value{0};
38
39public:
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.
69class FunctionFragment {
70 using BasicBlockListType = SmallVector<BinaryBasicBlock *, 0>;
71 using FragmentListType = SmallVector<unsigned, 0>;
72
73public:
74 using iterator = BasicBlockListType::iterator;
75 using const_iterator = BasicBlockListType::const_iterator;
76
77private:
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
104public:
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().
139class FunctionLayout {
140private:
141 using FragmentListType = SmallVector<FunctionFragment *, 0>;
142 using BasicBlockListType = SmallVector<BinaryBasicBlock *, 0>;
143
144public:
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
155private:
156 FragmentListType Fragments;
157 BasicBlockListType Blocks;
158
159public:
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
318private:
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

source code of bolt/include/bolt/Core/FunctionLayout.h