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
21namespace llvm {
22class MCSymbol;
23class raw_ostream;
24
25namespace bolt {
26
27enum 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
35class 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.
41class JumpTable : public BinaryData {
42 friend class BinaryContext;
43
44 JumpTable() = delete;
45 JumpTable(const JumpTable &) = delete;
46 JumpTable &operator=(const JumpTable &) = delete;
47
48public:
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
95private:
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
100public:
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

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