1 | //===- bolt/Core/JumpTable.h - Jump table at low-level IR -------*- 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 defines the JumpTable class, which represents a jump table in a |
10 | // binary file. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef BOLT_CORE_JUMP_TABLE_H |
15 | #define BOLT_CORE_JUMP_TABLE_H |
16 | |
17 | #include "bolt/Core/BinaryData.h" |
18 | #include <map> |
19 | #include <vector> |
20 | |
21 | namespace llvm { |
22 | class MCSymbol; |
23 | class raw_ostream; |
24 | |
25 | namespace bolt { |
26 | |
27 | enum JumpTableSupportLevel : char { |
28 | JTS_NONE = 0, /// Disable jump tables support. |
29 | JTS_BASIC = 1, /// Enable basic jump tables support (in-place). |
30 | JTS_MOVE = 2, /// Move jump tables to a separate section. |
31 | JTS_SPLIT = 3, /// Enable hot/cold splitting of jump tables. |
32 | JTS_AGGRESSIVE = 4, /// Aggressive splitting of jump tables. |
33 | }; |
34 | |
35 | class BinaryFunction; |
36 | |
37 | /// Representation of a jump table. |
38 | /// |
39 | /// The jump table may include other jump tables that are referenced by |
40 | /// a different label at a different offset in this jump table. |
41 | class JumpTable : public BinaryData { |
42 | friend class BinaryContext; |
43 | |
44 | JumpTable() = delete; |
45 | JumpTable(const JumpTable &) = delete; |
46 | JumpTable &operator=(const JumpTable &) = delete; |
47 | |
48 | public: |
49 | enum JumpTableType : char { |
50 | JTT_NORMAL, |
51 | JTT_PIC, |
52 | }; |
53 | |
54 | /// Branch statistics for jump table entries. |
55 | struct JumpInfo { |
56 | uint64_t Mispreds{0}; |
57 | uint64_t Count{0}; |
58 | }; |
59 | |
60 | /// Size of the entry used for storage. |
61 | size_t EntrySize; |
62 | |
63 | /// Size of the entry size we will write (we may use a more compact layout) |
64 | size_t OutputEntrySize; |
65 | |
66 | /// The type of this jump table. |
67 | JumpTableType Type; |
68 | |
69 | /// Whether this jump table has entries pointing to multiple functions. |
70 | bool IsSplit{false}; |
71 | |
72 | /// All the entries as labels. |
73 | std::vector<MCSymbol *> Entries; |
74 | |
75 | /// All the entries as absolute addresses. Invalid after disassembly is done. |
76 | using AddressesType = std::vector<uint64_t>; |
77 | AddressesType EntriesAsAddress; |
78 | |
79 | /// Map <Offset> -> <Label> used for embedded jump tables. Label at 0 offset |
80 | /// is the main label for the jump table. |
81 | using LabelMapType = std::map<unsigned, MCSymbol *>; |
82 | LabelMapType Labels; |
83 | |
84 | /// Dynamic number of times each entry in the table was referenced. |
85 | /// Identical entries will have a shared count (identical for every |
86 | /// entry in the set). |
87 | std::vector<JumpInfo> Counts; |
88 | |
89 | /// Total number of times this jump table was used. |
90 | uint64_t Count{0}; |
91 | |
92 | /// BinaryFunction this jump tables belongs to. |
93 | SmallVector<BinaryFunction *, 1> Parents; |
94 | |
95 | private: |
96 | /// Constructor should only be called by a BinaryContext. |
97 | JumpTable(MCSymbol &Symbol, uint64_t Address, size_t EntrySize, |
98 | JumpTableType Type, LabelMapType &&Labels, BinarySection &Section); |
99 | |
100 | public: |
101 | /// Return the size of the jump table. |
102 | uint64_t getSize() const { |
103 | return std::max(a: EntriesAsAddress.size(), b: Entries.size()) * EntrySize; |
104 | } |
105 | |
106 | const MCSymbol *getFirstLabel() const { |
107 | assert(Labels.count(0) != 0 && "labels must have an entry at 0" ); |
108 | return Labels.find(x: 0)->second; |
109 | } |
110 | |
111 | /// Get the indexes for symbol entries that correspond to the jump table |
112 | /// starting at (or containing) 'Addr'. |
113 | std::pair<size_t, size_t> getEntriesForAddress(const uint64_t Addr) const; |
114 | |
115 | bool isJumpTable() const override { return true; } |
116 | |
117 | /// Change all entries of the jump table in \p JTAddress pointing to |
118 | /// \p OldDest to \p NewDest. Return false if unsuccessful. |
119 | bool replaceDestination(uint64_t JTAddress, const MCSymbol *OldDest, |
120 | MCSymbol *NewDest); |
121 | |
122 | /// Update jump table at its original location. |
123 | void updateOriginal(); |
124 | |
125 | /// Print for debugging purposes. |
126 | void print(raw_ostream &OS) const override; |
127 | }; |
128 | |
129 | } // namespace bolt |
130 | } // namespace llvm |
131 | |
132 | #endif |
133 | |