1 //===- bolt/Core/JumpTable.cpp - Jump table at low-level IR ---------------===//
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 implements the JumpTable class.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "bolt/Core/JumpTable.h"
14 #include "bolt/Core/BinaryFunction.h"
15 #include "bolt/Core/BinarySection.h"
16 #include "llvm/Support/CommandLine.h"
17
18 #define DEBUG_TYPE "bolt"
19
20 using namespace llvm;
21 using namespace bolt;
22
23 using JumpTable = bolt::JumpTable;
24
25 namespace opts {
26 extern cl::opt<JumpTableSupportLevel> JumpTables;
27 extern cl::opt<unsigned> Verbosity;
28 } // namespace opts
29
JumpTable(MCSymbol & Symbol,uint64_t Address,size_t EntrySize,JumpTableType Type,LabelMapType && Labels,BinarySection & Section)30 bolt::JumpTable::JumpTable(MCSymbol &Symbol, uint64_t Address, size_t EntrySize,
31 JumpTableType Type, LabelMapType &&Labels,
32 BinarySection &Section)
33 : BinaryData(Symbol, Address, 0, EntrySize, Section), EntrySize(EntrySize),
34 OutputEntrySize(EntrySize), Type(Type), Labels(Labels) {}
35
36 std::pair<size_t, size_t>
getEntriesForAddress(const uint64_t Addr) const37 bolt::JumpTable::getEntriesForAddress(const uint64_t Addr) const {
38 // Check if this is not an address, but a cloned JT id
39 if ((int64_t)Addr < 0ll)
40 return std::make_pair(0, Entries.size());
41
42 const uint64_t InstOffset = Addr - getAddress();
43 size_t StartIndex = 0, EndIndex = 0;
44 uint64_t Offset = 0;
45
46 for (size_t I = 0; I < Entries.size(); ++I) {
47 auto LI = Labels.find(Offset);
48 if (LI != Labels.end()) {
49 const auto NextLI = std::next(LI);
50 const uint64_t NextOffset =
51 NextLI == Labels.end() ? getSize() : NextLI->first;
52 if (InstOffset >= LI->first && InstOffset < NextOffset) {
53 StartIndex = I;
54 EndIndex = I;
55 while (Offset < NextOffset) {
56 ++EndIndex;
57 Offset += EntrySize;
58 }
59 break;
60 }
61 }
62 Offset += EntrySize;
63 }
64
65 return std::make_pair(StartIndex, EndIndex);
66 }
67
replaceDestination(uint64_t JTAddress,const MCSymbol * OldDest,MCSymbol * NewDest)68 bool bolt::JumpTable::replaceDestination(uint64_t JTAddress,
69 const MCSymbol *OldDest,
70 MCSymbol *NewDest) {
71 bool Patched = false;
72 const std::pair<size_t, size_t> Range = getEntriesForAddress(JTAddress);
73 for (auto I = Range.first; I != Range.second; ++I) {
74 if (Entries[I] == OldDest) {
75 Patched = true;
76 Entries[I] = NewDest;
77 }
78 }
79 return Patched;
80 }
81
updateOriginal()82 void bolt::JumpTable::updateOriginal() {
83 BinaryContext &BC = getSection().getBinaryContext();
84 const uint64_t BaseOffset = getAddress() - getSection().getAddress();
85 uint64_t EntryOffset = BaseOffset;
86 for (MCSymbol *Entry : Entries) {
87 const uint64_t RelType =
88 Type == JTT_NORMAL ? ELF::R_X86_64_64 : ELF::R_X86_64_PC32;
89 const uint64_t RelAddend =
90 Type == JTT_NORMAL ? 0 : EntryOffset - BaseOffset;
91 // Replace existing relocation with the new one to allow any modifications
92 // to the original jump table.
93 if (BC.HasRelocations)
94 getOutputSection().removeRelocationAt(EntryOffset);
95 getOutputSection().addRelocation(EntryOffset, Entry, RelType, RelAddend);
96 EntryOffset += EntrySize;
97 }
98 }
99
print(raw_ostream & OS) const100 void bolt::JumpTable::print(raw_ostream &OS) const {
101 uint64_t Offset = 0;
102 if (Type == JTT_PIC)
103 OS << "PIC ";
104 ListSeparator LS;
105
106 OS << "Jump table " << getName() << " for function ";
107 for (BinaryFunction *Frag : Parents)
108 OS << LS << *Frag;
109 OS << " at 0x" << Twine::utohexstr(getAddress()) << " with a total count of "
110 << Count << ":\n";
111 for (const uint64_t EntryAddress : EntriesAsAddress)
112 OS << " absolute offset: 0x" << Twine::utohexstr(EntryAddress) << '\n';
113 for (const MCSymbol *Entry : Entries) {
114 auto LI = Labels.find(Offset);
115 if (Offset && LI != Labels.end()) {
116 OS << "Jump Table " << LI->second->getName() << " at 0x"
117 << Twine::utohexstr(getAddress() + Offset)
118 << " (possibly part of larger jump table):\n";
119 }
120 OS << format(" 0x%04" PRIx64 " : ", Offset) << Entry->getName();
121 if (!Counts.empty()) {
122 OS << " : " << Counts[Offset / EntrySize].Mispreds << "/"
123 << Counts[Offset / EntrySize].Count;
124 }
125 OS << '\n';
126 Offset += EntrySize;
127 }
128 OS << "\n\n";
129 }
130