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   /// All the entries as labels.
70   std::vector<MCSymbol *> Entries;
71 
72   /// All the entries as absolute addresses. Invalid after disassembly is done.
73   using AddressesType = std::vector<uint64_t>;
74   AddressesType EntriesAsAddress;
75 
76   /// Map <Offset> -> <Label> used for embedded jump tables. Label at 0 offset
77   /// is the main label for the jump table.
78   using LabelMapType = std::map<unsigned, MCSymbol *>;
79   LabelMapType Labels;
80 
81   /// Dynamic number of times each entry in the table was referenced.
82   /// Identical entries will have a shared count (identical for every
83   /// entry in the set).
84   std::vector<JumpInfo> Counts;
85 
86   /// Total number of times this jump table was used.
87   uint64_t Count{0};
88 
89   /// BinaryFunction this jump tables belongs to.
90   SmallVector<BinaryFunction *, 1> Parents;
91 
92 private:
93   /// Constructor should only be called by a BinaryContext.
94   JumpTable(MCSymbol &Symbol, uint64_t Address, size_t EntrySize,
95             JumpTableType Type, LabelMapType &&Labels, BinarySection &Section);
96 
97 public:
98   /// Return the size of the jump table.
getSize()99   uint64_t getSize() const {
100     return std::max(EntriesAsAddress.size(), Entries.size()) * EntrySize;
101   }
102 
getFirstLabel()103   const MCSymbol *getFirstLabel() const {
104     assert(Labels.count(0) != 0 && "labels must have an entry at 0");
105     return Labels.find(0)->second;
106   }
107 
108   /// Get the indexes for symbol entries that correspond to the jump table
109   /// starting at (or containing) 'Addr'.
110   std::pair<size_t, size_t> getEntriesForAddress(const uint64_t Addr) const;
111 
isJumpTable()112   virtual bool isJumpTable() const override { return true; }
113 
114   /// Change all entries of the jump table in \p JTAddress pointing to
115   /// \p OldDest to \p NewDest. Return false if unsuccessful.
116   bool replaceDestination(uint64_t JTAddress, const MCSymbol *OldDest,
117                           MCSymbol *NewDest);
118 
119   /// Update jump table at its original location.
120   void updateOriginal();
121 
122   /// Print for debugging purposes.
123   virtual void print(raw_ostream &OS) const override;
124 };
125 
126 } // namespace bolt
127 } // namespace llvm
128 
129 #endif
130