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