xref: /llvm-project/bolt/include/bolt/Core/JumpTable.h (revision 08ab4faf1aa338802ce7f482622dc020a2a26e08)
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.
getSize()102   uint64_t getSize() const {
103     return std::max(EntriesAsAddress.size(), Entries.size()) * EntrySize;
104   }
105 
getFirstLabel()106   const MCSymbol *getFirstLabel() const {
107     assert(Labels.count(0) != 0 && "labels must have an entry at 0");
108     return Labels.find(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 
isJumpTable()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