bolt/lib/Profile/BoltAddressTranslation.cpp

   1 //===- bolt/Profile/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 #include "bolt/Profile/BoltAddressTranslation.h"
  10 #include "bolt/Core/BinaryFunction.h"
  11 #include "llvm/ADT/APInt.h"
  12 #include "llvm/Support/Errc.h"
  13 #include "llvm/Support/Error.h"
  14 #include "llvm/Support/LEB128.h"
  15
  16 #define DEBUG_TYPE "bolt-bat"
  17
  18 namespace llvm {
  19 namespace bolt {
  20
  21 const char *BoltAddressTranslation::SECTION_NAME = ".note.bolt_bat";
  22
  23 void BoltAddressTranslation::writeEntriesForBB(
  24     MapTy &Map, const BinaryBasicBlock &BB, uint64_t FuncInputAddress,
  25     uint64_t FuncOutputAddress) const {
  26   const uint64_t BBOutputOffset =
  27       BB.getOutputAddressRange().first - FuncOutputAddress;
  28   const uint32_t BBInputOffset = BB.getInputOffset();
  29
  30   // Every output BB must track back to an input BB for profile collection
  31   // in bolted binaries. If we are missing an offset, it means this block was
  32   // created by a pass. We will skip writing any entries for it, and this means
  33   // any traffic happening in this block will map to the previous block in the
  34   // layout. This covers the case where an input basic block is split into two,
  35   // and the second one lacks any offset.
  36   if (BBInputOffset == BinaryBasicBlock::INVALID_OFFSET)
  37     return;
  38
  39   LLVM_DEBUG(dbgs() << "BB " << BB.getName() << "\n");
  40   LLVM_DEBUG(dbgs() << "  Key: " << Twine::utohexstr(BBOutputOffset)
  41                     << " Val: " << Twine::utohexstr(BBInputOffset) << "\n");
  42   // NB: in `writeEntriesForBB` we use the input address because hashes are
  43   // saved early in `saveMetadata` before output addresses are assigned.
  44   const BBHashMapTy &BBHashMap = getBBHashMap(FuncInputAddress);
  45   (void)BBHashMap;
  46   LLVM_DEBUG(
  47       dbgs() << formatv(" Hash: {0:x}\n", BBHashMap.getBBHash(BBInputOffset)));
  48   LLVM_DEBUG(
  49       dbgs() << formatv(" Index: {0}\n", BBHashMap.getBBIndex(BBInputOffset)));
  50   // In case of conflicts (same Key mapping to different Vals), the last
  51   // update takes precedence. Of course it is not ideal to have conflicts and
  52   // those happen when we have an empty BB that either contained only
  53   // NOPs or a jump to the next block (successor). Either way, the successor
  54   // and this deleted block will both share the same output address (the same
  55   // key), and we need to map back. We choose here to privilege the successor by
  56   // allowing it to overwrite the previously inserted key in the map.
  57   Map.emplace(BBOutputOffset, BBInputOffset << 1);
  58
  59   const auto &IOAddressMap =
  60       BB.getFunction()->getBinaryContext().getIOAddressMap();
  61
  62   for (const auto &[InputOffset, Sym] : BB.getLocSyms()) {
  63     const auto InputAddress = BB.getFunction()->getAddress() + InputOffset;
  64     const auto OutputAddress = IOAddressMap.lookup(InputAddress);
  65     assert(OutputAddress && "Unknown instruction address");
  66     const auto OutputOffset = *OutputAddress - FuncOutputAddress;
  67
  68     // Is this the first instruction in the BB? No need to duplicate the entry.
  69     if (OutputOffset == BBOutputOffset)
  70       continue;
  71
  72     LLVM_DEBUG(dbgs() << "  Key: " << Twine::utohexstr(OutputOffset) << " Val: "
  73                       << Twine::utohexstr(InputOffset) << " (branch)\n");
  74     Map.emplace(OutputOffset, (InputOffset << 1) | BRANCHENTRY);
  75   }
  76 }
  77
  78 void BoltAddressTranslation::write(const BinaryContext &BC, raw_ostream &OS) {
  79   LLVM_DEBUG(dbgs() << "BOLT-DEBUG: Writing BOLT Address Translation Tables\n");
  80   for (auto &BFI : BC.getBinaryFunctions()) {
  81     const BinaryFunction &Function = BFI.second;
  82     const uint64_t InputAddress = Function.getAddress();
  83     const uint64_t OutputAddress = Function.getOutputAddress();
  84     // We don't need a translation table if the body of the function hasn't
  85     // changed
  86     if (Function.isIgnored() || (!BC.HasRelocations && !Function.isSimple()))
  87       continue;
  88
  89     uint32_t NumSecondaryEntryPoints = 0;
  90     Function.forEachEntryPoint([&](uint64_t Offset, const MCSymbol *) {
  91       if (!Offset)
  92         return true;
  93       ++NumSecondaryEntryPoints;
  94       SecondaryEntryPointsMap[OutputAddress].push_back(Offset);
  95       return true;
  96     });
  97
  98     LLVM_DEBUG(dbgs() << "Function name: " << Function.getPrintName() << "\n");
  99     LLVM_DEBUG(dbgs() << " Address reference: 0x"
 100                       << Twine::utohexstr(Function.getOutputAddress()) << "\n");
 101     LLVM_DEBUG(dbgs() << formatv(" Hash: {0:x}\n", getBFHash(InputAddress)));
 102     LLVM_DEBUG(dbgs() << " Secondary Entry Points: " << NumSecondaryEntryPoints
 103                       << '\n');
 104
 105     MapTy Map;
 106     for (const BinaryBasicBlock *const BB :
 107          Function.getLayout().getMainFragment())
 108       writeEntriesForBB(Map, *BB, InputAddress, OutputAddress);
 109     // Add entries for deleted blocks. They are still required for correct BB
 110     // mapping of branches modified by SCTC. By convention, they would have the
 111     // end of the function as output address.
 112     const BBHashMapTy &BBHashMap = getBBHashMap(InputAddress);
 113     if (BBHashMap.size() != Function.size()) {
 114       const uint64_t EndOffset = Function.getOutputSize();
 115       std::unordered_set<uint32_t> MappedInputOffsets;
 116       for (const BinaryBasicBlock &BB : Function)
 117         MappedInputOffsets.emplace(BB.getInputOffset());
 118       for (const auto &[InputOffset, _] : BBHashMap)
 119         if (!llvm::is_contained(MappedInputOffsets, InputOffset))
 120           Map.emplace(EndOffset, InputOffset << 1);
 121     }
 122     Maps.emplace(Function.getOutputAddress(), std::move(Map));
 123     ReverseMap.emplace(OutputAddress, InputAddress);
 124
 125     if (!Function.isSplit())
 126       continue;
 127
 128     // Split maps
 129     LLVM_DEBUG(dbgs() << " Cold part\n");
 130     for (const FunctionFragment &FF :
 131          Function.getLayout().getSplitFragments()) {
 132       // Skip empty fragments to avoid adding zero-address entries to maps.
 133       if (FF.empty())
 134         continue;
 135       ColdPartSource.emplace(FF.getAddress(), Function.getOutputAddress());
 136       Map.clear();
 137       for (const BinaryBasicBlock *const BB : FF)
 138         writeEntriesForBB(Map, *BB, InputAddress, FF.getAddress());
 139
 140       Maps.emplace(FF.getAddress(), std::move(Map));
 141     }
 142   }
 143
 144   // Output addresses are delta-encoded
 145   uint64_t PrevAddress = 0;
 146   writeMaps</*Cold=*/false>(PrevAddress, OS);
 147   writeMaps</*Cold=*/true>(PrevAddress, OS);
 148
 149   BC.outs() << "BOLT-INFO: Wrote " << Maps.size() << " BAT maps\n";
 150   BC.outs() << "BOLT-INFO: Wrote " << FuncHashes.getNumFunctions()
 151             << " function and " << FuncHashes.getNumBasicBlocks()
 152             << " basic block hashes\n";
 153 }
 154
 155 APInt BoltAddressTranslation::calculateBranchEntriesBitMask(
 156     MapTy &Map, size_t EqualElems) const {
 157   APInt BitMask(alignTo(EqualElems, 8), 0);
 158   size_t Index = 0;
 159   for (std::pair<const uint32_t, uint32_t> &KeyVal : Map) {
 160     if (Index == EqualElems)
 161       break;
 162     const uint32_t OutputOffset = KeyVal.second;
 163     if (OutputOffset & BRANCHENTRY)
 164       BitMask.setBit(Index);
 165     ++Index;
 166   }
 167   return BitMask;
 168 }
 169
 170 size_t BoltAddressTranslation::getNumEqualOffsets(const MapTy &Map,
 171                                                   uint32_t Skew) const {
 172   size_t EqualOffsets = 0;
 173   for (const std::pair<const uint32_t, uint32_t> &KeyVal : Map) {
 174     const uint32_t OutputOffset = KeyVal.first;
 175     const uint32_t InputOffset = KeyVal.second >> 1;
 176     if (OutputOffset == InputOffset - Skew)
 177       ++EqualOffsets;
 178     else
 179       break;
 180   }
 181   return EqualOffsets;
 182 }
 183
 184 template <bool Cold>
 185 void BoltAddressTranslation::writeMaps(uint64_t &PrevAddress, raw_ostream &OS) {
 186   const uint32_t NumFuncs =
 187       llvm::count_if(llvm::make_first_range(Maps), [&](const uint64_t Address) {
 188         return Cold == ColdPartSource.count(Address);
 189       });
 190   encodeULEB128(NumFuncs, OS);
 191   LLVM_DEBUG(dbgs() << "Writing " << NumFuncs << (Cold ? " cold" : "")
 192                     << " functions for BAT.\n");
 193   size_t PrevIndex = 0;
 194   for (auto &MapEntry : Maps) {
 195     const uint64_t Address = MapEntry.first;
 196     // Only process cold fragments in cold mode, and vice versa.
 197     if (Cold != ColdPartSource.count(Address))
 198       continue;
 199     // NB: in `writeMaps` we use the input address because hashes are saved
 200     // early in `saveMetadata` before output addresses are assigned.
 201     const uint64_t HotInputAddress =
 202         ReverseMap[Cold ? ColdPartSource[Address] : Address];
 203     MapTy &Map = MapEntry.second;
 204     const uint32_t NumEntries = Map.size();
 205     LLVM_DEBUG(dbgs() << "Writing " << NumEntries << " entries for 0x"
 206                       << Twine::utohexstr(Address) << ".\n");
 207     encodeULEB128(Address - PrevAddress, OS);
 208     PrevAddress = Address;
 209     const uint32_t NumSecondaryEntryPoints =
 210         SecondaryEntryPointsMap.count(Address)
 211             ? SecondaryEntryPointsMap[Address].size()
 212             : 0;
 213     uint32_t Skew = 0;
 214     if (Cold) {
 215       auto HotEntryIt = llvm::lower_bound(HotFuncs, ColdPartSource[Address]);
 216       assert(HotEntryIt != HotFuncs.end());
 217       size_t HotIndex = std::distance(HotFuncs.begin(), HotEntryIt);
 218       encodeULEB128(HotIndex - PrevIndex, OS);
 219       PrevIndex = HotIndex;
 220       // Skew of all input offsets for cold fragments is simply the first input
 221       // offset.
 222       Skew = Map.begin()->second >> 1;
 223       encodeULEB128(Skew, OS);
 224     } else {
 225       HotFuncs.push_back(Address);
 226       // Function hash
 227       size_t BFHash = getBFHash(HotInputAddress);
 228       LLVM_DEBUG(dbgs() << "Hash: " << formatv("{0:x}\n", BFHash));
 229       OS.write(reinterpret_cast<char *>(&BFHash), 8);
 230       // Number of basic blocks
 231       size_t NumBasicBlocks = NumBasicBlocksMap[HotInputAddress];
 232       LLVM_DEBUG(dbgs() << "Basic blocks: " << NumBasicBlocks << '\n');
 233       encodeULEB128(NumBasicBlocks, OS);
 234       // Secondary entry points
 235       encodeULEB128(NumSecondaryEntryPoints, OS);
 236       LLVM_DEBUG(dbgs() << "Secondary Entry Points: " << NumSecondaryEntryPoints
 237                         << '\n');
 238     }
 239     encodeULEB128(NumEntries, OS);
 240     // Encode the number of equal offsets (output = input - skew) in the
 241     // beginning of the function. Only encode one offset in these cases.
 242     const size_t EqualElems = getNumEqualOffsets(Map, Skew);
 243     encodeULEB128(EqualElems, OS);
 244     if (EqualElems) {
 245       const size_t BranchEntriesBytes = alignTo(EqualElems, 8) / 8;
 246       APInt BranchEntries = calculateBranchEntriesBitMask(Map, EqualElems);
 247       OS.write(reinterpret_cast<const char *>(BranchEntries.getRawData()),
 248                BranchEntriesBytes);
 249       LLVM_DEBUG({
 250         dbgs() << "BranchEntries: ";
 251         SmallString<8> BitMaskStr;
 252         BranchEntries.toString(BitMaskStr, 2, false);
 253         dbgs() << BitMaskStr << '\n';
 254       });
 255     }
 256     const BBHashMapTy &BBHashMap = getBBHashMap(HotInputAddress);
 257     size_t Index = 0;
 258     uint64_t InOffset = 0;
 259     size_t PrevBBIndex = 0;
 260     // Output and Input addresses and delta-encoded
 261     for (std::pair<const uint32_t, uint32_t> &KeyVal : Map) {
 262       const uint64_t OutputAddress = KeyVal.first + Address;
 263       encodeULEB128(OutputAddress - PrevAddress, OS);
 264       PrevAddress = OutputAddress;
 265       if (Index++ >= EqualElems)
 266         encodeSLEB128(KeyVal.second - InOffset, OS);
 267       InOffset = KeyVal.second; // Keeping InOffset as if BRANCHENTRY is encoded
 268       if ((InOffset & BRANCHENTRY) == 0) {
 269         const bool IsBlock = BBHashMap.isInputBlock(InOffset >> 1);
 270         unsigned BBIndex = IsBlock ? BBHashMap.getBBIndex(InOffset >> 1) : 0;
 271         size_t BBHash = IsBlock ? BBHashMap.getBBHash(InOffset >> 1) : 0;
 272         OS.write(reinterpret_cast<char *>(&BBHash), 8);
 273         // Basic block index in the input binary
 274         encodeULEB128(BBIndex - PrevBBIndex, OS);
 275         PrevBBIndex = BBIndex;
 276         LLVM_DEBUG(dbgs() << formatv("{0:x} -> {1:x} {2:x} {3}\n", KeyVal.first,
 277                                      InOffset >> 1, BBHash, BBIndex));
 278       }
 279     }
 280     uint32_t PrevOffset = 0;
 281     if (!Cold && NumSecondaryEntryPoints) {
 282       LLVM_DEBUG(dbgs() << "Secondary entry points: ");
 283       // Secondary entry point offsets, delta-encoded
 284       for (uint32_t Offset : SecondaryEntryPointsMap[Address]) {
 285         encodeULEB128(Offset - PrevOffset, OS);
 286         LLVM_DEBUG(dbgs() << formatv("{0:x} ", Offset));
 287         PrevOffset = Offset;
 288       }
 289       LLVM_DEBUG(dbgs() << '\n');
 290     }
 291   }
 292 }
 293
 294 std::error_code BoltAddressTranslation::parse(raw_ostream &OS, StringRef Buf) {
 295   DataExtractor DE = DataExtractor(Buf, true, 8);
 296   uint64_t Offset = 0;
 297   if (Buf.size() < 12)
 298     return make_error_code(llvm::errc::io_error);
 299
 300   const uint32_t NameSz = DE.getU32(&Offset);
 301   const uint32_t DescSz = DE.getU32(&Offset);
 302   const uint32_t Type = DE.getU32(&Offset);
 303
 304   if (Type != BinarySection::NT_BOLT_BAT ||
 305       Buf.size() + Offset < alignTo(NameSz, 4) + DescSz)
 306     return make_error_code(llvm::errc::io_error);
 307
 308   StringRef Name = Buf.slice(Offset, Offset + NameSz);
 309   Offset = alignTo(Offset + NameSz, 4);
 310   if (!Name.starts_with("BOLT"))
 311     return make_error_code(llvm::errc::io_error);
 312
 313   Error Err(Error::success());
 314   uint64_t PrevAddress = 0;
 315   parseMaps</*Cold=*/false>(PrevAddress, DE, Offset, Err);
 316   parseMaps</*Cold=*/true>(PrevAddress, DE, Offset, Err);
 317   OS << "BOLT-INFO: Parsed " << Maps.size() << " BAT entries\n";
 318   return errorToErrorCode(std::move(Err));
 319 }
 320
 321 template <bool Cold>
 322 void BoltAddressTranslation::parseMaps(uint64_t &PrevAddress, DataExtractor &DE,
 323                                        uint64_t &Offset, Error &Err) {
 324   const uint32_t NumFunctions = DE.getULEB128(&Offset, &Err);
 325   LLVM_DEBUG(dbgs() << "Parsing " << NumFunctions << (Cold ? " cold" : "")
 326                     << " functions\n");
 327   size_t HotIndex = 0;
 328   for (uint32_t I = 0; I < NumFunctions; ++I) {
 329     const uint64_t Address = PrevAddress + DE.getULEB128(&Offset, &Err);
 330     uint64_t HotAddress = Cold ? 0 : Address;
 331     PrevAddress = Address;
 332     uint32_t SecondaryEntryPoints = 0;
 333     uint64_t ColdInputSkew = 0;
 334     if (Cold) {
 335       HotIndex += DE.getULEB128(&Offset, &Err);
 336       HotAddress = HotFuncs[HotIndex];
 337       ColdPartSource.emplace(Address, HotAddress);
 338       ColdInputSkew = DE.getULEB128(&Offset, &Err);
 339     } else {
 340       HotFuncs.push_back(Address);
 341       // Function hash
 342       const size_t FuncHash = DE.getU64(&Offset, &Err);
 343       FuncHashes.addEntry(Address, FuncHash);
 344       LLVM_DEBUG(dbgs() << formatv("{0:x}: hash {1:x}\n", Address, FuncHash));
 345       // Number of basic blocks
 346       const size_t NumBasicBlocks = DE.getULEB128(&Offset, &Err);
 347       NumBasicBlocksMap.emplace(Address, NumBasicBlocks);
 348       LLVM_DEBUG(dbgs() << formatv("{0:x}: #bbs {1}, {2} bytes\n", Address,
 349                                    NumBasicBlocks,
 350                                    getULEB128Size(NumBasicBlocks)));
 351       // Secondary entry points
 352       SecondaryEntryPoints = DE.getULEB128(&Offset, &Err);
 353       LLVM_DEBUG(
 354           dbgs() << formatv("{0:x}: secondary entry points {1}, {2} bytes\n",
 355                             Address, SecondaryEntryPoints,
 356                             getULEB128Size(SecondaryEntryPoints)));
 357     }
 358     const uint32_t NumEntries = DE.getULEB128(&Offset, &Err);
 359     // Equal offsets.
 360     const size_t EqualElems = DE.getULEB128(&Offset, &Err);
 361     APInt BEBitMask;
 362     LLVM_DEBUG(dbgs() << formatv("Equal offsets: {0}, {1} bytes\n", EqualElems,
 363                                  getULEB128Size(EqualElems)));
 364     if (EqualElems) {
 365       const size_t BranchEntriesBytes = alignTo(EqualElems, 8) / 8;
 366       BEBitMask = APInt(alignTo(EqualElems, 8), 0);
 367       LoadIntFromMemory(
 368           BEBitMask,
 369           reinterpret_cast<const uint8_t *>(
 370               DE.getBytes(&Offset, BranchEntriesBytes, &Err).data()),
 371           BranchEntriesBytes);
 372       LLVM_DEBUG({
 373         dbgs() << "BEBitMask: ";
 374         SmallString<8> BitMaskStr;
 375         BEBitMask.toString(BitMaskStr, 2, false);
 376         dbgs() << BitMaskStr << ", " << BranchEntriesBytes << " bytes\n";
 377       });
 378     }
 379     MapTy Map;
 380
 381     LLVM_DEBUG(dbgs() << "Parsing " << NumEntries << " entries for 0x"
 382                       << Twine::utohexstr(Address) << "\n");
 383     uint64_t InputOffset = 0;
 384     size_t BBIndex = 0;
 385     for (uint32_t J = 0; J < NumEntries; ++J) {
 386       const uint64_t OutputDelta = DE.getULEB128(&Offset, &Err);
 387       const uint64_t OutputAddress = PrevAddress + OutputDelta;
 388       const uint64_t OutputOffset = OutputAddress - Address;
 389       PrevAddress = OutputAddress;
 390       int64_t InputDelta = 0;
 391       if (J < EqualElems) {
 392         InputOffset = ((OutputOffset + ColdInputSkew) << 1) | BEBitMask[J];
 393       } else {
 394         InputDelta = DE.getSLEB128(&Offset, &Err);
 395         InputOffset += InputDelta;
 396       }
 397       Map.insert(std::pair<uint32_t, uint32_t>(OutputOffset, InputOffset));
 398       size_t BBHash = 0;
 399       size_t BBIndexDelta = 0;
 400       const bool IsBranchEntry = InputOffset & BRANCHENTRY;
 401       if (!IsBranchEntry) {
 402         BBHash = DE.getU64(&Offset, &Err);
 403         BBIndexDelta = DE.getULEB128(&Offset, &Err);
 404         BBIndex += BBIndexDelta;
 405         // Map basic block hash to hot fragment by input offset
 406         getBBHashMap(HotAddress).addEntry(InputOffset >> 1, BBIndex, BBHash);
 407       }
 408       LLVM_DEBUG({
 409         dbgs() << formatv(
 410             "{0:x} -> {1:x} ({2}/{3}b -> {4}/{5}b), {6:x}", OutputOffset,
 411             InputOffset, OutputDelta, getULEB128Size(OutputDelta), InputDelta,
 412             (J < EqualElems) ? 0 : getSLEB128Size(InputDelta), OutputAddress);
 413         if (!IsBranchEntry) {
 414           dbgs() << formatv(" {0:x} {1}/{2}b", BBHash, BBIndex,
 415                             getULEB128Size(BBIndexDelta));
 416         }
 417         dbgs() << '\n';
 418       });
 419     }
 420     Maps.insert(std::pair<uint64_t, MapTy>(Address, Map));
 421     if (!Cold && SecondaryEntryPoints) {
 422       uint32_t EntryPointOffset = 0;
 423       LLVM_DEBUG(dbgs() << "Secondary entry points: ");
 424       for (uint32_t EntryPointId = 0; EntryPointId != SecondaryEntryPoints;
 425            ++EntryPointId) {
 426         uint32_t OffsetDelta = DE.getULEB128(&Offset, &Err);
 427         EntryPointOffset += OffsetDelta;
 428         SecondaryEntryPointsMap[Address].push_back(EntryPointOffset);
 429         LLVM_DEBUG(dbgs() << formatv("{0:x}/{1}b ", EntryPointOffset,
 430                                      getULEB128Size(OffsetDelta)));
 431       }
 432       LLVM_DEBUG(dbgs() << '\n');
 433     }
 434   }
 435 }
 436
 437 void BoltAddressTranslation::dump(raw_ostream &OS) const {
 438   const size_t NumTables = Maps.size();
 439   OS << "BAT tables for " << NumTables << " functions:\n";
 440   for (const auto &MapEntry : Maps) {
 441     const uint64_t Address = MapEntry.first;
 442     const uint64_t HotAddress = fetchParentAddress(Address);
 443     const bool IsHotFunction = HotAddress == 0;
 444     OS << "Function Address: 0x" << Twine::utohexstr(Address);
 445     if (IsHotFunction)
 446       OS << formatv(", hash: {0:x}", getBFHash(Address));
 447     OS << "\n";
 448     OS << "BB mappings:\n";
 449     const BBHashMapTy &BBHashMap =
 450         getBBHashMap(HotAddress ? HotAddress : Address);
 451     for (const auto &Entry : MapEntry.second) {
 452       const bool IsBranch = Entry.second & BRANCHENTRY;
 453       const uint32_t Val = Entry.second >> 1; // dropping BRANCHENTRY bit
 454       OS << "0x" << Twine::utohexstr(Entry.first) << " -> "
 455          << "0x" << Twine::utohexstr(Val);
 456       if (IsBranch)
 457         OS << " (branch)";
 458       else
 459         OS << formatv(" hash: {0:x}", BBHashMap.getBBHash(Val));
 460       OS << "\n";
 461     }
 462     if (IsHotFunction) {
 463       auto NumBasicBlocksIt = NumBasicBlocksMap.find(Address);
 464       assert(NumBasicBlocksIt != NumBasicBlocksMap.end());
 465       OS << "NumBlocks: " << NumBasicBlocksIt->second << '\n';
 466     }
 467     auto SecondaryEntryPointsIt = SecondaryEntryPointsMap.find(Address);
 468     if (SecondaryEntryPointsIt != SecondaryEntryPointsMap.end()) {
 469       const std::vector<uint32_t> &SecondaryEntryPoints =
 470           SecondaryEntryPointsIt->second;
 471       OS << SecondaryEntryPoints.size() << " secondary entry points:\n";
 472       for (uint32_t EntryPointOffset : SecondaryEntryPoints)
 473         OS << formatv("{0:x}\n", EntryPointOffset);
 474     }
 475     OS << "\n";
 476   }
 477   const size_t NumColdParts = ColdPartSource.size();
 478   if (!NumColdParts)
 479     return;
 480
 481   OS << NumColdParts << " cold mappings:\n";
 482   for (const auto &Entry : ColdPartSource) {
 483     OS << "0x" << Twine::utohexstr(Entry.first) << " -> "
 484        << Twine::utohexstr(Entry.second) << "\n";
 485   }
 486   OS << "\n";
 487 }
 488
 489 uint64_t BoltAddressTranslation::translate(uint64_t FuncAddress,
 490                                            uint64_t Offset,
 491                                            bool IsBranchSrc) const {
 492   auto Iter = Maps.find(FuncAddress);
 493   if (Iter == Maps.end())
 494     return Offset;
 495
 496   const MapTy &Map = Iter->second;
 497   auto KeyVal = Map.upper_bound(Offset);
 498   if (KeyVal == Map.begin())
 499     return Offset;
 500
 501   --KeyVal;
 502
 503   const uint32_t Val = KeyVal->second >> 1; // dropping BRANCHENTRY bit
 504   // Branch source addresses are translated to the first instruction of the
 505   // source BB to avoid accounting for modifications BOLT may have made in the
 506   // BB regarding deletion/addition of instructions.
 507   if (IsBranchSrc)
 508     return Val;
 509   return Offset - KeyVal->first + Val;
 510 }
 511
 512 std::optional<BoltAddressTranslation::FallthroughListTy>
 513 BoltAddressTranslation::getFallthroughsInTrace(uint64_t FuncAddress,
 514                                                uint64_t From,
 515                                                uint64_t To) const {
 516   SmallVector<std::pair<uint64_t, uint64_t>, 16> Res;
 517
 518   // Filter out trivial case
 519   if (From >= To)
 520     return Res;
 521
 522   From -= FuncAddress;
 523   To -= FuncAddress;
 524
 525   auto Iter = Maps.find(FuncAddress);
 526   if (Iter == Maps.end())
 527     return std::nullopt;
 528
 529   const MapTy &Map = Iter->second;
 530   auto FromIter = Map.upper_bound(From);
 531   if (FromIter == Map.begin())
 532     return Res;
 533   // Skip instruction entries, to create fallthroughs we are only interested in
 534   // BB boundaries
 535   do {
 536     if (FromIter == Map.begin())
 537       return Res;
 538     --FromIter;
 539   } while (FromIter->second & BRANCHENTRY);
 540
 541   auto ToIter = Map.upper_bound(To);
 542   if (ToIter == Map.begin())
 543     return Res;
 544   --ToIter;
 545   if (FromIter->first >= ToIter->first)
 546     return Res;
 547
 548   for (auto Iter = FromIter; Iter != ToIter;) {
 549     const uint32_t Src = Iter->first;
 550     if (Iter->second & BRANCHENTRY) {
 551       ++Iter;
 552       continue;
 553     }
 554
 555     ++Iter;
 556     while (Iter->second & BRANCHENTRY && Iter != ToIter)
 557       ++Iter;
 558     if (Iter->second & BRANCHENTRY)
 559       break;
 560     Res.emplace_back(Src, Iter->first);
 561   }
 562
 563   return Res;
 564 }
 565
 566 bool BoltAddressTranslation::enabledFor(
 567     llvm::object::ELFObjectFileBase *InputFile) const {
 568   for (const SectionRef &Section : InputFile->sections()) {
 569     Expected<StringRef> SectionNameOrErr = Section.getName();
 570     if (Error E = SectionNameOrErr.takeError())
 571       continue;
 572
 573     if (SectionNameOrErr.get() == SECTION_NAME)
 574       return true;
 575   }
 576   return false;
 577 }
 578
 579 void BoltAddressTranslation::saveMetadata(BinaryContext &BC) {
 580   for (BinaryFunction &BF : llvm::make_second_range(BC.getBinaryFunctions())) {
 581     // We don't need a translation table if the body of the function hasn't
 582     // changed
 583     if (BF.isIgnored() || (!BC.HasRelocations && !BF.isSimple()))
 584       continue;
 585     // Prepare function and block hashes
 586     FuncHashes.addEntry(BF.getAddress(), BF.computeHash());
 587     BF.computeBlockHashes();
 588     BBHashMapTy &BBHashMap = getBBHashMap(BF.getAddress());
 589     // Set BF/BB metadata
 590     for (const BinaryBasicBlock &BB : BF)
 591       BBHashMap.addEntry(BB.getInputOffset(), BB.getIndex(), BB.getHash());
 592     NumBasicBlocksMap.emplace(BF.getAddress(), BF.size());
 593   }
 594 }
 595
 596 unsigned
 597 BoltAddressTranslation::getSecondaryEntryPointId(uint64_t Address,
 598                                                  uint32_t Offset) const {
 599   auto FunctionIt = SecondaryEntryPointsMap.find(Address);
 600   if (FunctionIt == SecondaryEntryPointsMap.end())
 601     return 0;
 602   const std::vector<uint32_t> &Offsets = FunctionIt->second;
 603   auto OffsetIt = std::find(Offsets.begin(), Offsets.end(), Offset);
 604   if (OffsetIt == Offsets.end())
 605     return 0;
 606   // Adding one here because main entry point is not stored in BAT, and
 607   // enumeration for secondary entry points starts with 1.
 608   return OffsetIt - Offsets.begin() + 1;
 609 }
 610
 611 std::pair<const BinaryFunction *, unsigned>
 612 BoltAddressTranslation::translateSymbol(const BinaryContext &BC,
 613                                         const MCSymbol &Symbol,
 614                                         uint32_t Offset) const {
 615   // The symbol could be a secondary entry in a cold fragment.
 616   uint64_t SymbolValue = cantFail(errorOrToExpected(BC.getSymbolValue(Symbol)));
 617
 618   const BinaryFunction *Callee = BC.getFunctionForSymbol(&Symbol);
 619   assert(Callee);
 620
 621   // Containing function, not necessarily the same as symbol value.
 622   const uint64_t CalleeAddress = Callee->getAddress();
 623   const uint32_t OutputOffset = SymbolValue - CalleeAddress;
 624
 625   const uint64_t ParentAddress = fetchParentAddress(CalleeAddress);
 626   const uint64_t HotAddress = ParentAddress ? ParentAddress : CalleeAddress;
 627
 628   const BinaryFunction *ParentBF = BC.getBinaryFunctionAtAddress(HotAddress);
 629
 630   const uint32_t InputOffset =
 631       translate(CalleeAddress, OutputOffset, /*IsBranchSrc*/ false) + Offset;
 632
 633   unsigned SecondaryEntryId{0};
 634   if (InputOffset)
 635     SecondaryEntryId = getSecondaryEntryPointId(HotAddress, InputOffset);
 636
 637   return std::pair(ParentBF, SecondaryEntryId);
 638 }
 639
 640 } // namespace bolt
 641 } // namespace llvm