xref: /llvm-project/bolt/lib/Profile/BoltAddressTranslation.cpp (revision a34c753fe709a624f5b087397fb05adeac2311e4) 
1 //===--- BoltAddressTranslation.cpp ---------------------------------------===//
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 //===----------------------------------------------------------------------===//
10 #include "bolt/Profile/BoltAddressTranslation.h"
11 #include "bolt/Core/BinaryFunction.h"
12 #include "llvm/Support/DataExtractor.h"
13 #include "llvm/Support/Errc.h"
14 
15 #define DEBUG_TYPE "bolt-bat"
16 
17 namespace llvm {
18 namespace bolt {
19 
20 const char* BoltAddressTranslation::SECTION_NAME = ".note.bolt_bat";
21 
22 void BoltAddressTranslation::writeEntriesForBB(MapTy &Map,
23                                                const BinaryBasicBlock &BB,
24                                                uint64_t FuncAddress) {
25   const uint64_t BBOutputOffset =
26       BB.getOutputAddressRange().first - FuncAddress;
27   const uint32_t BBInputOffset = BB.getInputOffset();
28 
29   assert(BBInputOffset != BinaryBasicBlock::INVALID_OFFSET &&
30          "Every output BB must track back to an input BB for profile "
31          "collection in bolted binaries");
32 
33   LLVM_DEBUG(dbgs() << "BB " << BB.getName() << "\n");
34   LLVM_DEBUG(dbgs() << "  Key: " << Twine::utohexstr(BBOutputOffset)
35                     << " Val: " << Twine::utohexstr(BBInputOffset) << "\n");
36   // In case of conflicts (same Key mapping to different Vals), the last
37   // update takes precedence. Of course it is not ideal to have conflicts and
38   // those happen when we have an empty BB that either contained only
39   // NOPs or a jump to the next block (successor). Either way, the successor
40   // and this deleted block will both share the same output address (the same
41   // key), and we need to map back. We choose here to privilege the successor by
42   // allowing it to overwrite the previously inserted key in the map.
43   Map[BBOutputOffset] = BBInputOffset;
44 
45   for (const auto &IOPair : BB.getOffsetTranslationTable()) {
46     const uint64_t OutputOffset = IOPair.first + BBOutputOffset;
47     const uint32_t InputOffset = IOPair.second;
48 
49     // Is this the first instruction in the BB? No need to duplicate the entry.
50     if (OutputOffset == BBOutputOffset)
51       continue;
52 
53     LLVM_DEBUG(dbgs() << "  Key: " << Twine::utohexstr(OutputOffset) << " Val: "
54                       << Twine::utohexstr(InputOffset) << " (branch)\n");
55     Map.insert(
56         std::pair<uint32_t, uint32_t>(OutputOffset, InputOffset | BRANCHENTRY));
57   }
58 }
59 
60 void BoltAddressTranslation::write(raw_ostream &OS) {
61   LLVM_DEBUG(dbgs() << "BOLT-DEBUG: Writing BOLT Address Translation Tables\n");
62   for (auto &BFI : BC.getBinaryFunctions()) {
63     BinaryFunction &Function = BFI.second;
64     // We don't need a translation table if the body of the function hasn't
65     // changed
66     if (!BC.HasRelocations && !Function.isSimple())
67       continue;
68 
69     LLVM_DEBUG(dbgs() << "Function name: " << Function.getPrintName() << "\n");
70     LLVM_DEBUG(dbgs() << " Address reference: 0x"
71                       << Twine::utohexstr(Function.getOutputAddress()) << "\n");
72     MapTy Map;
73     const bool IsSplit = Function.isSplit();
74     for (BinaryBasicBlock *&BB : Function.layout()) {
75       if (IsSplit && BB->isCold())
76         break;
77       writeEntriesForBB(Map, *BB, Function.getOutputAddress());
78     }
79     Maps.insert(std::pair<uint64_t, MapTy>(Function.getOutputAddress(), Map));
80 
81     if (!IsSplit)
82       continue;
83 
84     // Cold map
85     Map.clear();
86     LLVM_DEBUG(dbgs() << " Cold part\n");
87     for (BinaryBasicBlock *&BB : Function.layout()) {
88       if (!BB->isCold())
89         continue;
90       writeEntriesForBB(Map, *BB, Function.cold().getAddress());
91     }
92     Maps.insert(std::pair<uint64_t, MapTy>(Function.cold().getAddress(), Map));
93     ColdPartSource.insert(std::pair<uint64_t, uint64_t>(
94         Function.cold().getAddress(), Function.getOutputAddress()));
95   }
96 
97   const uint32_t NumFuncs = Maps.size();
98   OS.write(reinterpret_cast<const char *>(&NumFuncs), 4);
99   LLVM_DEBUG(dbgs() << "Writing " << NumFuncs << " functions for BAT.\n");
100   for (auto &MapEntry : Maps) {
101     const uint64_t Address = MapEntry.first;
102     MapTy &Map = MapEntry.second;
103     const uint32_t NumEntries = Map.size();
104     LLVM_DEBUG(dbgs() << "Writing " << NumEntries << " entries for 0x"
105                       << Twine::utohexstr(Address) << ".\n");
106     OS.write(reinterpret_cast<const char *>(&Address), 8);
107     OS.write(reinterpret_cast<const char *>(&NumEntries), 4);
108     for (std::pair<const uint32_t, uint32_t> &KeyVal : Map) {
109       OS.write(reinterpret_cast<const char *>(&KeyVal.first), 4);
110       OS.write(reinterpret_cast<const char *>(&KeyVal.second), 4);
111     }
112   }
113   const uint32_t NumColdEntries = ColdPartSource.size();
114   LLVM_DEBUG(dbgs() << "Writing " << NumColdEntries
115                     << " cold part mappings.\n");
116   OS.write(reinterpret_cast<const char *>(&NumColdEntries), 4);
117   for (std::pair<const uint64_t, uint64_t> &ColdEntry : ColdPartSource) {
118     OS.write(reinterpret_cast<const char *>(&ColdEntry.first), 8);
119     OS.write(reinterpret_cast<const char *>(&ColdEntry.second), 8);
120     LLVM_DEBUG(dbgs() << " " << Twine::utohexstr(ColdEntry.first) << " -> "
121                       << Twine::utohexstr(ColdEntry.second) << "\n");
122   }
123 
124   outs() << "BOLT-INFO: Wrote " << Maps.size() << " BAT maps\n";
125   outs() << "BOLT-INFO: Wrote " << NumColdEntries
126          << " BAT cold-to-hot entries\n";
127 }
128 
129 std::error_code BoltAddressTranslation::parse(StringRef Buf) {
130   DataExtractor DE = DataExtractor(Buf, true, 8);
131   uint64_t Offset = 0;
132   if (Buf.size() < 12)
133     return make_error_code(llvm::errc::io_error);
134 
135   const uint32_t NameSz = DE.getU32(&Offset);
136   const uint32_t DescSz = DE.getU32(&Offset);
137   const uint32_t Type = DE.getU32(&Offset);
138 
139   if (Type != BinarySection::NT_BOLT_BAT ||
140       Buf.size() + Offset < alignTo(NameSz, 4) + DescSz)
141     return make_error_code(llvm::errc::io_error);
142 
143   StringRef Name = Buf.slice(Offset, Offset + NameSz);
144   Offset = alignTo(Offset + NameSz, 4);
145   if (Name.substr(0, 4) != "BOLT")
146     return make_error_code(llvm::errc::io_error);
147 
148   if (Buf.size() - Offset < 4)
149     return make_error_code(llvm::errc::io_error);
150 
151   const uint32_t NumFunctions = DE.getU32(&Offset);
152   LLVM_DEBUG(dbgs() << "Parsing " << NumFunctions << " functions\n");
153   for (uint32_t I = 0; I < NumFunctions; ++I) {
154     if (Buf.size() - Offset < 12)
155       return make_error_code(llvm::errc::io_error);
156 
157     const uint64_t Address = DE.getU64(&Offset);
158     const uint32_t NumEntries = DE.getU32(&Offset);
159     MapTy Map;
160 
161     LLVM_DEBUG(dbgs() << "Parsing " << NumEntries << " entries for 0x"
162                       << Twine::utohexstr(Address) << "\n");
163     if (Buf.size() - Offset < 8 * NumEntries)
164       return make_error_code(llvm::errc::io_error);
165     for (uint32_t J = 0; J < NumEntries; ++J) {
166       const uint32_t OutputAddr = DE.getU32(&Offset);
167       const uint32_t InputAddr = DE.getU32(&Offset);
168       Map.insert(std::pair<uint32_t, uint32_t>(OutputAddr, InputAddr));
169       LLVM_DEBUG(dbgs() << Twine::utohexstr(OutputAddr) << " -> "
170                         << Twine::utohexstr(InputAddr) << "\n");
171     }
172     Maps.insert(std::pair<uint64_t, MapTy>(Address, Map));
173   }
174 
175   if (Buf.size() - Offset < 4)
176     return make_error_code(llvm::errc::io_error);
177 
178   const uint32_t NumColdEntries = DE.getU32(&Offset);
179   LLVM_DEBUG(dbgs() << "Parsing " << NumColdEntries << " cold part mappings\n");
180   for (uint32_t I = 0; I < NumColdEntries; ++I) {
181     if (Buf.size() - Offset < 16)
182       return make_error_code(llvm::errc::io_error);
183     const uint32_t ColdAddress = DE.getU64(&Offset);
184     const uint32_t HotAddress = DE.getU64(&Offset);
185     ColdPartSource.insert(
186         std::pair<uint64_t, uint64_t>(ColdAddress, HotAddress));
187     LLVM_DEBUG(dbgs() << Twine::utohexstr(ColdAddress) << " -> "
188                       << Twine::utohexstr(HotAddress) << "\n");
189   }
190   outs() << "BOLT-INFO: Parsed " << Maps.size() << " BAT entries\n";
191   outs() << "BOLT-INFO: Parsed " << NumColdEntries
192          << " BAT cold-to-hot entries\n";
193 
194   return std::error_code();
195 }
196 
197 uint64_t BoltAddressTranslation::translate(const BinaryFunction &Func,
198                                            uint64_t Offset,
199                                            bool IsBranchSrc) const {
200   auto Iter = Maps.find(Func.getAddress());
201   if (Iter == Maps.end())
202     return Offset;
203 
204   const MapTy &Map = Iter->second;
205   auto KeyVal = Map.upper_bound(Offset);
206   if (KeyVal == Map.begin())
207     return Offset;
208 
209   --KeyVal;
210 
211   const uint32_t Val = KeyVal->second & ~BRANCHENTRY;
212   // Branch source addresses are translated to the first instruction of the
213   // source BB to avoid accounting for modifications BOLT may have made in the
214   // BB regarding deletion/addition of instructions.
215   if (IsBranchSrc)
216     return Val;
217   return Offset - KeyVal->first + Val;
218 }
219 
220 Optional<BoltAddressTranslation::FallthroughListTy>
221 BoltAddressTranslation::getFallthroughsInTrace(
222     const BinaryFunction &Func, uint64_t From, uint64_t To) const {
223   SmallVector<std::pair<uint64_t, uint64_t>, 16> Res;
224 
225   // Filter out trivial case
226   if (From >= To)
227     return Res;
228 
229   From -= Func.getAddress();
230   To -= Func.getAddress();
231 
232   auto Iter = Maps.find(Func.getAddress());
233   if (Iter == Maps.end()) {
234     return NoneType();
235   }
236 
237   const MapTy &Map = Iter->second;
238   auto FromIter = Map.upper_bound(From);
239   if (FromIter == Map.begin())
240     return Res;
241   // Skip instruction entries, to create fallthroughs we are only interested in
242   // BB boundaries
243   do {
244     if (FromIter == Map.begin())
245       return Res;
246     --FromIter;
247   } while (FromIter->second & BRANCHENTRY);
248 
249   auto ToIter = Map.upper_bound(To);
250   if (ToIter == Map.begin())
251     return Res;
252   --ToIter;
253   if (FromIter->first >= ToIter->first)
254     return Res;
255 
256   for (auto Iter = FromIter; Iter != ToIter; ) {
257     const uint32_t Src = Iter->first;
258     if (Iter->second & BRANCHENTRY) {
259       ++Iter;
260       continue;
261     }
262 
263     ++Iter;
264     while (Iter->second & BRANCHENTRY && Iter != ToIter) {
265       ++Iter;
266     }
267     if (Iter->second & BRANCHENTRY)
268       break;
269     Res.emplace_back(Src, Iter->first);
270   }
271 
272   return Res;
273 }
274 
275 uint64_t BoltAddressTranslation::fetchParentAddress(uint64_t Address) const {
276   auto Iter = ColdPartSource.find(Address);
277   if (Iter == ColdPartSource.end())
278     return 0;
279   return Iter->second;
280 }
281 
282 bool BoltAddressTranslation::enabledFor(
283     llvm::object::ELFObjectFileBase *InputFile) const {
284   for (const SectionRef &Section : InputFile->sections()) {
285     Expected<StringRef> SectionNameOrErr = Section.getName();
286     if (Error E = SectionNameOrErr.takeError())
287       continue;
288 
289     if (SectionNameOrErr.get() == SECTION_NAME)
290       return true;
291   }
292   return false;
293 }
294 }
295 }
296