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