bolt/lib/Profile/DataReader.cpp

   1 //===- bolt/Profile/DataReader.cpp - Perf data reader ---------------------===//
   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 family of functions reads profile data written by the perf2bolt
  10 // utility and stores it in memory for llvm-bolt consumption.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "bolt/Profile/DataReader.h"
  15 #include "bolt/Core/BinaryFunction.h"
  16 #include "bolt/Passes/MCF.h"
  17 #include "bolt/Utils/Utils.h"
  18 #include "llvm/Support/CommandLine.h"
  19 #include "llvm/Support/Debug.h"
  20 #include "llvm/Support/Errc.h"
  21 #include <map>
  22
  23 #undef  DEBUG_TYPE
  24 #define DEBUG_TYPE "bolt-prof"
  25
  26 using namespace llvm;
  27
  28 namespace opts {
  29
  30 extern cl::OptionCategory BoltCategory;
  31 extern llvm::cl::opt<unsigned> Verbosity;
  32
  33 static cl::opt<bool>
  34 DumpData("dump-data",
  35   cl::desc("dump parsed bolt data for debugging"),
  36   cl::Hidden,
  37   cl::cat(BoltCategory));
  38
  39 } // namespace opts
  40
  41 namespace llvm {
  42 namespace bolt {
  43
  44 namespace {
  45
  46 /// Return true if the function name can change across compilations.
  47 bool hasVolatileName(const BinaryFunction &BF) {
  48   for (const StringRef &Name : BF.getNames())
  49     if (getLTOCommonName(Name))
  50       return true;
  51
  52   return false;
  53 }
  54
  55 /// Return standard escaped name of the function possibly renamed by BOLT.
  56 std::string normalizeName(StringRef NameRef) {
  57   // Strip "PG." prefix used for globalized locals.
  58   NameRef = NameRef.startswith("PG.") ? NameRef.substr(2) : NameRef;
  59   return getEscapedName(NameRef);
  60 }
  61
  62 } // anonymous namespace
  63
  64 raw_ostream &operator<<(raw_ostream &OS, const Location &Loc) {
  65   if (Loc.IsSymbol) {
  66     OS << Loc.Name;
  67     if (Loc.Offset)
  68       OS << "+" << Twine::utohexstr(Loc.Offset);
  69   } else {
  70     OS << Twine::utohexstr(Loc.Offset);
  71   }
  72   return OS;
  73 }
  74
  75 void FuncBranchData::appendFrom(const FuncBranchData &FBD, uint64_t Offset) {
  76   Data.insert(Data.end(), FBD.Data.begin(), FBD.Data.end());
  77   for (auto I = Data.begin(), E = Data.end(); I != E; ++I) {
  78     if (I->From.Name == FBD.Name) {
  79       I->From.Name = this->Name;
  80       I->From.Offset += Offset;
  81     }
  82     if (I->To.Name == FBD.Name) {
  83       I->To.Name = this->Name;
  84       I->To.Offset += Offset;
  85     }
  86   }
  87   llvm::stable_sort(Data);
  88   ExecutionCount += FBD.ExecutionCount;
  89   for (auto I = FBD.EntryData.begin(), E = FBD.EntryData.end(); I != E; ++I) {
  90     assert(I->To.Name == FBD.Name);
  91     auto NewElmt = EntryData.insert(EntryData.end(), *I);
  92     NewElmt->To.Name = this->Name;
  93     NewElmt->To.Offset += Offset;
  94   }
  95 }
  96
  97 uint64_t FuncBranchData::getNumExecutedBranches() const {
  98   uint64_t ExecutedBranches = 0;
  99   for (const BranchInfo &BI : Data) {
 100     int64_t BranchCount = BI.Branches;
 101     assert(BranchCount >= 0 && "branch execution count should not be negative");
 102     ExecutedBranches += BranchCount;
 103   }
 104   return ExecutedBranches;
 105 }
 106
 107 void SampleInfo::mergeWith(const SampleInfo &SI) { Hits += SI.Hits; }
 108
 109 void SampleInfo::print(raw_ostream &OS) const {
 110   OS << Loc.IsSymbol << " " << Loc.Name << " " << Twine::utohexstr(Loc.Offset)
 111      << " " << Hits << "\n";
 112 }
 113
 114 uint64_t FuncSampleData::getSamples(uint64_t Start, uint64_t End) const {
 115   assert(llvm::is_sorted(Data));
 116   struct Compare {
 117     bool operator()(const SampleInfo &SI, const uint64_t Val) const {
 118       return SI.Loc.Offset < Val;
 119     }
 120     bool operator()(const uint64_t Val, const SampleInfo &SI) const {
 121       return Val < SI.Loc.Offset;
 122     }
 123   };
 124   uint64_t Result = 0;
 125   for (auto I = llvm::lower_bound(Data, Start, Compare()),
 126             E = llvm::lower_bound(Data, End, Compare());
 127        I != E; ++I)
 128     Result += I->Hits;
 129   return Result;
 130 }
 131
 132 void FuncSampleData::bumpCount(uint64_t Offset, uint64_t Count) {
 133   auto Iter = Index.find(Offset);
 134   if (Iter == Index.end()) {
 135     Data.emplace_back(Location(true, Name, Offset), Count);
 136     Index[Offset] = Data.size() - 1;
 137     return;
 138   }
 139   SampleInfo &SI = Data[Iter->second];
 140   SI.Hits += Count;
 141 }
 142
 143 void FuncBranchData::bumpBranchCount(uint64_t OffsetFrom, uint64_t OffsetTo,
 144                                      uint64_t Count, uint64_t Mispreds) {
 145   auto Iter = IntraIndex[OffsetFrom].find(OffsetTo);
 146   if (Iter == IntraIndex[OffsetFrom].end()) {
 147     Data.emplace_back(Location(true, Name, OffsetFrom),
 148                       Location(true, Name, OffsetTo), Mispreds, Count);
 149     IntraIndex[OffsetFrom][OffsetTo] = Data.size() - 1;
 150     return;
 151   }
 152   BranchInfo &BI = Data[Iter->second];
 153   BI.Branches += Count;
 154   BI.Mispreds += Mispreds;
 155 }
 156
 157 void FuncBranchData::bumpCallCount(uint64_t OffsetFrom, const Location &To,
 158                                    uint64_t Count, uint64_t Mispreds) {
 159   auto Iter = InterIndex[OffsetFrom].find(To);
 160   if (Iter == InterIndex[OffsetFrom].end()) {
 161     Data.emplace_back(Location(true, Name, OffsetFrom), To, Mispreds, Count);
 162     InterIndex[OffsetFrom][To] = Data.size() - 1;
 163     return;
 164   }
 165   BranchInfo &BI = Data[Iter->second];
 166   BI.Branches += Count;
 167   BI.Mispreds += Mispreds;
 168 }
 169
 170 void FuncBranchData::bumpEntryCount(const Location &From, uint64_t OffsetTo,
 171                                     uint64_t Count, uint64_t Mispreds) {
 172   auto Iter = EntryIndex[OffsetTo].find(From);
 173   if (Iter == EntryIndex[OffsetTo].end()) {
 174     EntryData.emplace_back(From, Location(true, Name, OffsetTo), Mispreds,
 175                            Count);
 176     EntryIndex[OffsetTo][From] = EntryData.size() - 1;
 177     return;
 178   }
 179   BranchInfo &BI = EntryData[Iter->second];
 180   BI.Branches += Count;
 181   BI.Mispreds += Mispreds;
 182 }
 183
 184 void BranchInfo::mergeWith(const BranchInfo &BI) {
 185   Branches += BI.Branches;
 186   Mispreds += BI.Mispreds;
 187 }
 188
 189 void BranchInfo::print(raw_ostream &OS) const {
 190   OS << From.IsSymbol << " " << From.Name << " "
 191      << Twine::utohexstr(From.Offset) << " " << To.IsSymbol << " " << To.Name
 192      << " " << Twine::utohexstr(To.Offset) << " " << Mispreds << " " << Branches
 193      << '\n';
 194 }
 195
 196 ErrorOr<const BranchInfo &> FuncBranchData::getBranch(uint64_t From,
 197                                                       uint64_t To) const {
 198   for (const BranchInfo &I : Data)
 199     if (I.From.Offset == From && I.To.Offset == To && I.From.Name == I.To.Name)
 200       return I;
 201
 202   return make_error_code(llvm::errc::invalid_argument);
 203 }
 204
 205 ErrorOr<const BranchInfo &>
 206 FuncBranchData::getDirectCallBranch(uint64_t From) const {
 207   // Commented out because it can be expensive.
 208   // assert(std::is_sorted(Data.begin(), Data.end()));
 209   struct Compare {
 210     bool operator()(const BranchInfo &BI, const uint64_t Val) const {
 211       return BI.From.Offset < Val;
 212     }
 213     bool operator()(const uint64_t Val, const BranchInfo &BI) const {
 214       return Val < BI.From.Offset;
 215     }
 216   };
 217   auto Range = std::equal_range(Data.begin(), Data.end(), From, Compare());
 218   for (const auto &RI : llvm::make_range(Range))
 219     if (RI.From.Name != RI.To.Name)
 220       return RI;
 221
 222   return make_error_code(llvm::errc::invalid_argument);
 223 }
 224
 225 void MemInfo::print(raw_ostream &OS) const {
 226   OS << (Offset.IsSymbol + 3) << " " << Offset.Name << " "
 227      << Twine::utohexstr(Offset.Offset) << " " << (Addr.IsSymbol + 3) << " "
 228      << Addr.Name << " " << Twine::utohexstr(Addr.Offset) << " " << Count
 229      << "\n";
 230 }
 231
 232 void MemInfo::prettyPrint(raw_ostream &OS) const {
 233   OS << "(PC: " << Offset << ", M: " << Addr << ", C: " << Count << ")";
 234 }
 235
 236 void FuncMemData::update(const Location &Offset, const Location &Addr) {
 237   auto Iter = EventIndex[Offset.Offset].find(Addr);
 238   if (Iter == EventIndex[Offset.Offset].end()) {
 239     Data.emplace_back(MemInfo(Offset, Addr, 1));
 240     EventIndex[Offset.Offset][Addr] = Data.size() - 1;
 241     return;
 242   }
 243   ++Data[Iter->second].Count;
 244 }
 245
 246 Error DataReader::preprocessProfile(BinaryContext &BC) {
 247   if (std::error_code EC = parseInput())
 248     return errorCodeToError(EC);
 249
 250   if (opts::DumpData)
 251     dump();
 252
 253   if (collectedInBoltedBinary())
 254     outs() << "BOLT-INFO: profile collection done on a binary already "
 255               "processed by BOLT\n";
 256
 257   for (auto &BFI : BC.getBinaryFunctions()) {
 258     BinaryFunction &Function = BFI.second;
 259     if (FuncMemData *MemData = getMemDataForNames(Function.getNames())) {
 260       setMemData(Function, MemData);
 261       MemData->Used = true;
 262     }
 263     if (FuncBranchData *FuncData = getBranchDataForNames(Function.getNames())) {
 264       setBranchData(Function, FuncData);
 265       Function.ExecutionCount = FuncData->ExecutionCount;
 266       FuncData->Used = true;
 267     }
 268   }
 269
 270   for (auto &BFI : BC.getBinaryFunctions()) {
 271     BinaryFunction &Function = BFI.second;
 272     matchProfileMemData(Function);
 273   }
 274
 275   return Error::success();
 276 }
 277
 278 Error DataReader::readProfilePreCFG(BinaryContext &BC) {
 279   for (auto &BFI : BC.getBinaryFunctions()) {
 280     BinaryFunction &Function = BFI.second;
 281     FuncMemData *MemoryData = getMemData(Function);
 282     if (!MemoryData)
 283       continue;
 284
 285     for (MemInfo &MI : MemoryData->Data) {
 286       const uint64_t Offset = MI.Offset.Offset;
 287       auto II = Function.Instructions.find(Offset);
 288       if (II == Function.Instructions.end()) {
 289         // Ignore bad instruction address.
 290         continue;
 291       }
 292
 293       auto &MemAccessProfile =
 294           BC.MIB->getOrCreateAnnotationAs<MemoryAccessProfile>(
 295               II->second, "MemoryAccessProfile");
 296       BinaryData *BD = nullptr;
 297       if (MI.Addr.IsSymbol)
 298         BD = BC.getBinaryDataByName(MI.Addr.Name);
 299       MemAccessProfile.AddressAccessInfo.push_back(
 300           {BD, MI.Addr.Offset, MI.Count});
 301       auto NextII = std::next(II);
 302       if (NextII == Function.Instructions.end())
 303         MemAccessProfile.NextInstrOffset = Function.getSize();
 304       else
 305         MemAccessProfile.NextInstrOffset = II->first;
 306     }
 307     Function.HasMemoryProfile = true;
 308   }
 309
 310   return Error::success();
 311 }
 312
 313 Error DataReader::readProfile(BinaryContext &BC) {
 314   for (auto &BFI : BC.getBinaryFunctions()) {
 315     BinaryFunction &Function = BFI.second;
 316     readProfile(Function);
 317   }
 318
 319   uint64_t NumUnused = 0;
 320   for (const auto &KV : NamesToBranches) {
 321     const FuncBranchData &FBD = KV.second;
 322     if (!FBD.Used)
 323       ++NumUnused;
 324   }
 325   BC.setNumUnusedProfiledObjects(NumUnused);
 326
 327   return Error::success();
 328 }
 329
 330 std::error_code DataReader::parseInput() {
 331   ErrorOr<std::unique_ptr<MemoryBuffer>> MB =
 332       MemoryBuffer::getFileOrSTDIN(Filename);
 333   if (std::error_code EC = MB.getError()) {
 334     Diag << "cannot open " << Filename << ": " << EC.message() << "\n";
 335     return EC;
 336   }
 337   FileBuf = std::move(MB.get());
 338   ParsingBuf = FileBuf->getBuffer();
 339   if (std::error_code EC = parse())
 340     return EC;
 341   if (!ParsingBuf.empty())
 342     Diag << "WARNING: invalid profile data detected at line " << Line
 343          << ". Possibly corrupted profile.\n";
 344
 345   buildLTONameMaps();
 346
 347   return std::error_code();
 348 }
 349
 350 void DataReader::readProfile(BinaryFunction &BF) {
 351   if (BF.empty())
 352     return;
 353
 354   if (!hasLBR()) {
 355     BF.ProfileFlags = BinaryFunction::PF_SAMPLE;
 356     readSampleData(BF);
 357     return;
 358   }
 359
 360   BF.ProfileFlags = BinaryFunction::PF_LBR;
 361
 362   // Possibly assign/re-assign branch profile data.
 363   matchProfileData(BF);
 364
 365   FuncBranchData *FBD = getBranchData(BF);
 366   if (!FBD)
 367     return;
 368
 369   // Assign basic block counts to function entry points. These only include
 370   // counts for outside entries.
 371   //
 372   // There is a slight skew introduced here as branches originated from RETs
 373   // may be accounted for in the execution count of an entry block if the last
 374   // instruction in a predecessor fall-through block is a call. This situation
 375   // should rarely happen because there are few multiple-entry functions.
 376   for (const BranchInfo &BI : FBD->EntryData) {
 377     BinaryBasicBlock *BB = BF.getBasicBlockAtOffset(BI.To.Offset);
 378     if (BB && (BB->isEntryPoint() || BB->isLandingPad())) {
 379       uint64_t Count = BB->getExecutionCount();
 380       if (Count == BinaryBasicBlock::COUNT_NO_PROFILE)
 381         Count = 0;
 382       BB->setExecutionCount(Count + BI.Branches);
 383     }
 384   }
 385
 386   for (const BranchInfo &BI : FBD->Data) {
 387     if (BI.From.Name != BI.To.Name)
 388       continue;
 389
 390     if (!recordBranch(BF, BI.From.Offset, BI.To.Offset, BI.Branches,
 391                       BI.Mispreds)) {
 392       LLVM_DEBUG(dbgs() << "bad branch : " << BI.From.Offset << " -> "
 393                         << BI.To.Offset << '\n');
 394     }
 395   }
 396
 397   // Convert branch data into annotations.
 398   convertBranchData(BF);
 399 }
 400
 401 void DataReader::matchProfileData(BinaryFunction &BF) {
 402   // This functionality is available for LBR-mode only
 403   // TODO: Implement evaluateProfileData() for samples, checking whether
 404   // sample addresses match instruction addresses in the function
 405   if (!hasLBR())
 406     return;
 407
 408   FuncBranchData *FBD = getBranchData(BF);
 409   if (FBD) {
 410     BF.ProfileMatchRatio = evaluateProfileData(BF, *FBD);
 411     BF.RawBranchCount = FBD->getNumExecutedBranches();
 412     if (BF.ProfileMatchRatio == 1.0f) {
 413       if (fetchProfileForOtherEntryPoints(BF)) {
 414         BF.ProfileMatchRatio = evaluateProfileData(BF, *FBD);
 415         BF.ExecutionCount = FBD->ExecutionCount;
 416         BF.RawBranchCount = FBD->getNumExecutedBranches();
 417       }
 418       return;
 419     }
 420   }
 421
 422   // Check if the function name can fluctuate between several compilations
 423   // possibly triggered by minor unrelated code changes in the source code
 424   // of the input binary.
 425   if (!hasVolatileName(BF))
 426     return;
 427
 428   // Check for a profile that matches with 100% confidence.
 429   const std::vector<FuncBranchData *> AllBranchData =
 430       getBranchDataForNamesRegex(BF.getNames());
 431   for (FuncBranchData *NewBranchData : AllBranchData) {
 432     // Prevent functions from sharing the same profile.
 433     if (NewBranchData->Used)
 434       continue;
 435
 436     if (evaluateProfileData(BF, *NewBranchData) != 1.0f)
 437       continue;
 438
 439     if (FBD)
 440       FBD->Used = false;
 441
 442     // Update function profile data with the new set.
 443     setBranchData(BF, NewBranchData);
 444     NewBranchData->Used = true;
 445     BF.ExecutionCount = NewBranchData->ExecutionCount;
 446     BF.ProfileMatchRatio = 1.0f;
 447     break;
 448   }
 449 }
 450
 451 void DataReader::matchProfileMemData(BinaryFunction &BF) {
 452   const std::vector<FuncMemData *> AllMemData =
 453       getMemDataForNamesRegex(BF.getNames());
 454   for (FuncMemData *NewMemData : AllMemData) {
 455     // Prevent functions from sharing the same profile.
 456     if (NewMemData->Used)
 457       continue;
 458
 459     if (FuncMemData *MD = getMemData(BF))
 460       MD->Used = false;
 461
 462     // Update function profile data with the new set.
 463     setMemData(BF, NewMemData);
 464     NewMemData->Used = true;
 465     break;
 466   }
 467 }
 468
 469 bool DataReader::fetchProfileForOtherEntryPoints(BinaryFunction &BF) {
 470   BinaryContext &BC = BF.getBinaryContext();
 471
 472   FuncBranchData *FBD = getBranchData(BF);
 473   if (!FBD)
 474     return false;
 475
 476   // Check if we are missing profiling data for secondary entry points
 477   bool First = true;
 478   bool Updated = false;
 479   for (BinaryBasicBlock *BB : BF.BasicBlocks) {
 480     if (First) {
 481       First = false;
 482       continue;
 483     }
 484     if (BB->isEntryPoint()) {
 485       uint64_t EntryAddress = BB->getOffset() + BF.getAddress();
 486       // Look for branch data associated with this entry point
 487       if (BinaryData *BD = BC.getBinaryDataAtAddress(EntryAddress)) {
 488         if (FuncBranchData *Data = getBranchDataForSymbols(BD->getSymbols())) {
 489           FBD->appendFrom(*Data, BB->getOffset());
 490           Data->Used = true;
 491           Updated = true;
 492         }
 493       }
 494     }
 495   }
 496
 497   return Updated;
 498 }
 499
 500 float DataReader::evaluateProfileData(BinaryFunction &BF,
 501                                       const FuncBranchData &BranchData) const {
 502   BinaryContext &BC = BF.getBinaryContext();
 503
 504   // Until we define a minimal profile, we consider an empty branch data to be
 505   // a valid profile. It could happen to a function without branches when we
 506   // still have an EntryData for the execution count.
 507   if (BranchData.Data.empty())
 508     return 1.0f;
 509
 510   uint64_t NumMatchedBranches = 0;
 511   for (const BranchInfo &BI : BranchData.Data) {
 512     bool IsValid = false;
 513     if (BI.From.Name == BI.To.Name) {
 514       // Try to record information with 0 count.
 515       IsValid = recordBranch(BF, BI.From.Offset, BI.To.Offset, 0);
 516     } else if (collectedInBoltedBinary()) {
 517       // We can't check branch source for collections in bolted binaries because
 518       // the source of the branch may be mapped to the first instruction in a BB
 519       // instead of the original branch (which may not exist in the source bin).
 520       IsValid = true;
 521     } else {
 522       // The branch has to originate from this function.
 523       // Check for calls, tail calls, rets and indirect branches.
 524       // When matching profiling info, we did not reach the stage
 525       // when we identify tail calls, so they are still represented
 526       // by regular branch instructions and we need isBranch() here.
 527       MCInst *Instr = BF.getInstructionAtOffset(BI.From.Offset);
 528       // If it's a prefix - skip it.
 529       if (Instr && BC.MIB->isPrefix(*Instr))
 530         Instr = BF.getInstructionAtOffset(BI.From.Offset + 1);
 531       if (Instr && (BC.MIB->isCall(*Instr) || BC.MIB->isBranch(*Instr) ||
 532                     BC.MIB->isReturn(*Instr)))
 533         IsValid = true;
 534     }
 535
 536     if (IsValid) {
 537       ++NumMatchedBranches;
 538       continue;
 539     }
 540
 541     LLVM_DEBUG(dbgs() << "\tinvalid branch in " << BF << " : 0x"
 542                       << Twine::utohexstr(BI.From.Offset) << " -> ";
 543                if (BI.From.Name == BI.To.Name) dbgs()
 544                << "0x" << Twine::utohexstr(BI.To.Offset) << '\n';
 545                else dbgs() << "<outbounds>\n";);
 546   }
 547
 548   const float MatchRatio = (float)NumMatchedBranches / BranchData.Data.size();
 549   if (opts::Verbosity >= 2 && NumMatchedBranches < BranchData.Data.size())
 550     errs() << "BOLT-WARNING: profile branches match only "
 551            << format("%.1f%%", MatchRatio * 100.0f) << " ("
 552            << NumMatchedBranches << '/' << BranchData.Data.size()
 553            << ") for function " << BF << '\n';
 554
 555   return MatchRatio;
 556 }
 557
 558 void DataReader::readSampleData(BinaryFunction &BF) {
 559   FuncSampleData *SampleDataOrErr = getFuncSampleData(BF.getNames());
 560   if (!SampleDataOrErr)
 561     return;
 562
 563   // Basic samples mode territory (without LBR info)
 564   // First step is to assign BB execution count based on samples from perf
 565   BF.ProfileMatchRatio = 1.0f;
 566   BF.removeTagsFromProfile();
 567   bool NormalizeByInsnCount = usesEvent("cycles") || usesEvent("instructions");
 568   bool NormalizeByCalls = usesEvent("branches");
 569   static bool NagUser = true;
 570   if (NagUser) {
 571     outs()
 572         << "BOLT-INFO: operating with basic samples profiling data (no LBR).\n";
 573     if (NormalizeByInsnCount)
 574       outs() << "BOLT-INFO: normalizing samples by instruction count.\n";
 575     else if (NormalizeByCalls)
 576       outs() << "BOLT-INFO: normalizing samples by branches.\n";
 577
 578     NagUser = false;
 579   }
 580   uint64_t LastOffset = BF.getSize();
 581   uint64_t TotalEntryCount = 0;
 582   for (BinaryFunction::BasicBlockOffset &BBOffset :
 583        llvm::reverse(BF.BasicBlockOffsets)) {
 584     uint64_t CurOffset = BBOffset.first;
 585     // Always work with samples multiplied by 1000 to avoid losing them if we
 586     // later need to normalize numbers
 587     uint64_t NumSamples =
 588         SampleDataOrErr->getSamples(CurOffset, LastOffset) * 1000;
 589     if (NormalizeByInsnCount && BBOffset.second->getNumNonPseudos()) {
 590       NumSamples /= BBOffset.second->getNumNonPseudos();
 591     } else if (NormalizeByCalls) {
 592       uint32_t NumCalls = BBOffset.second->getNumCalls();
 593       NumSamples /= NumCalls + 1;
 594     }
 595     BBOffset.second->setExecutionCount(NumSamples);
 596     if (BBOffset.second->isEntryPoint())
 597       TotalEntryCount += NumSamples;
 598     LastOffset = CurOffset;
 599   }
 600
 601   BF.ExecutionCount = TotalEntryCount;
 602
 603   estimateEdgeCounts(BF);
 604 }
 605
 606 void DataReader::convertBranchData(BinaryFunction &BF) const {
 607   BinaryContext &BC = BF.getBinaryContext();
 608
 609   if (BF.empty())
 610     return;
 611
 612   FuncBranchData *FBD = getBranchData(BF);
 613   if (!FBD)
 614     return;
 615
 616   // Profile information for calls.
 617   //
 618   // There are 3 cases that we annotate differently:
 619   //   1) Conditional tail calls that could be mispredicted.
 620   //   2) Indirect calls to multiple destinations with mispredictions.
 621   //      Before we validate CFG we have to handle indirect branches here too.
 622   //   3) Regular direct calls. The count could be different from containing
 623   //      basic block count. Keep this data in case we find it useful.
 624   //
 625   for (BranchInfo &BI : FBD->Data) {
 626     // Ignore internal branches.
 627     if (BI.To.IsSymbol && BI.To.Name == BI.From.Name && BI.To.Offset != 0)
 628       continue;
 629
 630     MCInst *Instr = BF.getInstructionAtOffset(BI.From.Offset);
 631     if (!Instr ||
 632         (!BC.MIB->isCall(*Instr) && !BC.MIB->isIndirectBranch(*Instr)))
 633       continue;
 634
 635     auto setOrUpdateAnnotation = [&](StringRef Name, uint64_t Count) {
 636       if (opts::Verbosity >= 1 && BC.MIB->hasAnnotation(*Instr, Name))
 637         errs() << "BOLT-WARNING: duplicate " << Name << " info for offset 0x"
 638                << Twine::utohexstr(BI.From.Offset) << " in function " << BF
 639                << '\n';
 640       auto &Value = BC.MIB->getOrCreateAnnotationAs<uint64_t>(*Instr, Name);
 641       Value += Count;
 642     };
 643
 644     if (BC.MIB->isIndirectCall(*Instr) || BC.MIB->isIndirectBranch(*Instr)) {
 645       IndirectCallSiteProfile &CSP =
 646           BC.MIB->getOrCreateAnnotationAs<IndirectCallSiteProfile>(
 647               *Instr, "CallProfile");
 648       MCSymbol *CalleeSymbol = nullptr;
 649       if (BI.To.IsSymbol) {
 650         if (BinaryData *BD = BC.getBinaryDataByName(BI.To.Name))
 651           CalleeSymbol = BD->getSymbol();
 652       }
 653       CSP.emplace_back(CalleeSymbol, BI.Branches, BI.Mispreds);
 654     } else if (BC.MIB->getConditionalTailCall(*Instr)) {
 655       setOrUpdateAnnotation("CTCTakenCount", BI.Branches);
 656       setOrUpdateAnnotation("CTCMispredCount", BI.Mispreds);
 657     } else {
 658       setOrUpdateAnnotation("Count", BI.Branches);
 659     }
 660   }
 661 }
 662
 663 bool DataReader::recordBranch(BinaryFunction &BF, uint64_t From, uint64_t To,
 664                               uint64_t Count, uint64_t Mispreds) const {
 665   BinaryContext &BC = BF.getBinaryContext();
 666
 667   BinaryBasicBlock *FromBB = BF.getBasicBlockContainingOffset(From);
 668   const BinaryBasicBlock *ToBB = BF.getBasicBlockContainingOffset(To);
 669
 670   if (!FromBB || !ToBB) {
 671     LLVM_DEBUG(dbgs() << "failed to get block for recorded branch\n");
 672     return false;
 673   }
 674
 675   // Could be bad LBR data; ignore the branch. In the case of data collected
 676   // in binaries optimized by BOLT, a source BB may be mapped to two output
 677   // BBs as a result of optimizations. In that case, a branch between these
 678   // two will be recorded as a branch from A going to A in the source address
 679   // space. Keep processing.
 680   if (From == To)
 681     return true;
 682
 683   // Return from a tail call.
 684   if (FromBB->succ_size() == 0)
 685     return true;
 686
 687   // Very rarely we will see ignored branches. Do a linear check.
 688   for (std::pair<uint32_t, uint32_t> &Branch : BF.IgnoredBranches)
 689     if (Branch ==
 690         std::make_pair(static_cast<uint32_t>(From), static_cast<uint32_t>(To)))
 691       return true;
 692
 693   bool OffsetMatches = !!(To == ToBB->getOffset());
 694   if (!OffsetMatches) {
 695     // Skip the nops to support old .fdata
 696     uint64_t Offset = ToBB->getOffset();
 697     for (const MCInst &Instr : *ToBB) {
 698       if (!BC.MIB->isNoop(Instr))
 699         break;
 700
 701       Offset += BC.MIB->getAnnotationWithDefault<uint32_t>(Instr, "Size");
 702     }
 703
 704     if (To == Offset)
 705       OffsetMatches = true;
 706   }
 707
 708   if (!OffsetMatches) {
 709     // "To" could be referring to nop instructions in between 2 basic blocks.
 710     // While building the CFG we make sure these nops are attributed to the
 711     // previous basic block, thus we check if the destination belongs to the
 712     // gap past the last instruction.
 713     const MCInst *LastInstr = ToBB->getLastNonPseudoInstr();
 714     if (LastInstr) {
 715       const uint32_t LastInstrOffset =
 716           BC.MIB->getOffsetWithDefault(*LastInstr, 0);
 717
 718       // With old .fdata we are getting FT branches for "jcc,jmp" sequences.
 719       if (To == LastInstrOffset && BC.MIB->isUnconditionalBranch(*LastInstr))
 720         return true;
 721
 722       if (To <= LastInstrOffset) {
 723         LLVM_DEBUG(dbgs() << "branch recorded into the middle of the block"
 724                           << " in " << BF << " : " << From << " -> " << To
 725                           << '\n');
 726         return false;
 727       }
 728     }
 729
 730     // The real destination is the layout successor of the detected ToBB.
 731     if (ToBB == BF.getLayout().block_back())
 732       return false;
 733     const BinaryBasicBlock *NextBB =
 734         BF.getLayout().getBlock(ToBB->getIndex() + 1);
 735     assert((NextBB && NextBB->getOffset() > ToBB->getOffset()) && "bad layout");
 736     ToBB = NextBB;
 737   }
 738
 739   // If there's no corresponding instruction for 'From', we have probably
 740   // discarded it as a FT from __builtin_unreachable.
 741   MCInst *FromInstruction = BF.getInstructionAtOffset(From);
 742   if (!FromInstruction) {
 743     // If the data was collected in a bolted binary, the From addresses may be
 744     // translated to the first instruction of the source BB if BOLT inserted
 745     // a new branch that did not exist in the source (we can't map it to the
 746     // source instruction, so we map it to the first instr of source BB).
 747     // We do not keep offsets for random instructions. So the check above will
 748     // evaluate to true if the first instr is not a branch (call/jmp/ret/etc)
 749     if (collectedInBoltedBinary()) {
 750       if (FromBB->getInputOffset() != From) {
 751         LLVM_DEBUG(dbgs() << "offset " << From << " does not match a BB in "
 752                           << BF << '\n');
 753         return false;
 754       }
 755       FromInstruction = nullptr;
 756     } else {
 757       LLVM_DEBUG(dbgs() << "no instruction for offset " << From << " in " << BF
 758                         << '\n');
 759       return false;
 760     }
 761   }
 762
 763   if (!FromBB->getSuccessor(ToBB->getLabel())) {
 764     // Check if this is a recursive call or a return from a recursive call.
 765     if (FromInstruction && ToBB->isEntryPoint() &&
 766         (BC.MIB->isCall(*FromInstruction) ||
 767          BC.MIB->isIndirectBranch(*FromInstruction))) {
 768       // Execution count is already accounted for.
 769       return true;
 770     }
 771     // For data collected in a bolted binary, we may have created two output BBs
 772     // that map to one original block. Branches between these two blocks will
 773     // appear here as one BB jumping to itself, even though it has no loop
 774     // edges. Ignore these.
 775     if (collectedInBoltedBinary() && FromBB == ToBB)
 776       return true;
 777
 778     BinaryBasicBlock *FTSuccessor = FromBB->getConditionalSuccessor(false);
 779     if (FTSuccessor && FTSuccessor->succ_size() == 1 &&
 780         FTSuccessor->getSuccessor(ToBB->getLabel())) {
 781       BinaryBasicBlock::BinaryBranchInfo &FTBI =
 782           FTSuccessor->getBranchInfo(*ToBB);
 783       FTBI.Count += Count;
 784       if (Count)
 785         FTBI.MispredictedCount += Mispreds;
 786       ToBB = FTSuccessor;
 787     } else {
 788       LLVM_DEBUG(dbgs() << "invalid branch in " << BF
 789                         << formatv(": {0:x} -> {1:x}\n", From, To));
 790       return false;
 791     }
 792   }
 793
 794   BinaryBasicBlock::BinaryBranchInfo &BI = FromBB->getBranchInfo(*ToBB);
 795   BI.Count += Count;
 796   // Only update mispredicted count if it the count was real.
 797   if (Count) {
 798     BI.MispredictedCount += Mispreds;
 799   }
 800
 801   return true;
 802 }
 803
 804 void DataReader::reportError(StringRef ErrorMsg) {
 805   Diag << "Error reading BOLT data input file: line " << Line << ", column "
 806        << Col << ": " << ErrorMsg << '\n';
 807 }
 808
 809 bool DataReader::expectAndConsumeFS() {
 810   if (ParsingBuf[0] != FieldSeparator) {
 811     reportError("expected field separator");
 812     return false;
 813   }
 814   ParsingBuf = ParsingBuf.drop_front(1);
 815   Col += 1;
 816   return true;
 817 }
 818
 819 void DataReader::consumeAllRemainingFS() {
 820   while (ParsingBuf[0] == FieldSeparator) {
 821     ParsingBuf = ParsingBuf.drop_front(1);
 822     Col += 1;
 823   }
 824 }
 825
 826 bool DataReader::checkAndConsumeNewLine() {
 827   if (ParsingBuf[0] != '\n')
 828     return false;
 829
 830   ParsingBuf = ParsingBuf.drop_front(1);
 831   Col = 0;
 832   Line += 1;
 833   return true;
 834 }
 835
 836 ErrorOr<StringRef> DataReader::parseString(char EndChar, bool EndNl) {
 837   if (EndChar == '\\') {
 838     reportError("EndChar could not be backslash");
 839     return make_error_code(llvm::errc::io_error);
 840   }
 841
 842   std::string EndChars(1, EndChar);
 843   EndChars.push_back('\\');
 844   if (EndNl)
 845     EndChars.push_back('\n');
 846
 847   size_t StringEnd = 0;
 848   do {
 849     StringEnd = ParsingBuf.find_first_of(EndChars, StringEnd);
 850     if (StringEnd == StringRef::npos ||
 851         (StringEnd == 0 && ParsingBuf[StringEnd] != '\\')) {
 852       reportError("malformed field");
 853       return make_error_code(llvm::errc::io_error);
 854     }
 855
 856     if (ParsingBuf[StringEnd] != '\\')
 857       break;
 858
 859     StringEnd += 2;
 860   } while (true);
 861
 862   StringRef Str = ParsingBuf.substr(0, StringEnd);
 863
 864   // If EndNl was set and nl was found instead of EndChar, do not consume the
 865   // new line.
 866   bool EndNlInsteadOfEndChar = ParsingBuf[StringEnd] == '\n' && EndChar != '\n';
 867   unsigned End = EndNlInsteadOfEndChar ? StringEnd : StringEnd + 1;
 868
 869   ParsingBuf = ParsingBuf.drop_front(End);
 870   if (EndChar == '\n') {
 871     Col = 0;
 872     Line += 1;
 873   } else {
 874     Col += End;
 875   }
 876   return Str;
 877 }
 878
 879 ErrorOr<int64_t> DataReader::parseNumberField(char EndChar, bool EndNl) {
 880   ErrorOr<StringRef> NumStrRes = parseString(EndChar, EndNl);
 881   if (std::error_code EC = NumStrRes.getError())
 882     return EC;
 883   StringRef NumStr = NumStrRes.get();
 884   int64_t Num;
 885   if (NumStr.getAsInteger(10, Num)) {
 886     reportError("expected decimal number");
 887     Diag << "Found: " << NumStr << "\n";
 888     return make_error_code(llvm::errc::io_error);
 889   }
 890   return Num;
 891 }
 892
 893 ErrorOr<uint64_t> DataReader::parseHexField(char EndChar, bool EndNl) {
 894   ErrorOr<StringRef> NumStrRes = parseString(EndChar, EndNl);
 895   if (std::error_code EC = NumStrRes.getError())
 896     return EC;
 897   StringRef NumStr = NumStrRes.get();
 898   uint64_t Num;
 899   if (NumStr.getAsInteger(16, Num)) {
 900     reportError("expected hexidecimal number");
 901     Diag << "Found: " << NumStr << "\n";
 902     return make_error_code(llvm::errc::io_error);
 903   }
 904   return Num;
 905 }
 906
 907 ErrorOr<Location> DataReader::parseLocation(char EndChar, bool EndNl,
 908                                             bool ExpectMemLoc) {
 909   // Read whether the location of the branch should be DSO or a symbol
 910   // 0 means it is a DSO. 1 means it is a global symbol. 2 means it is a local
 911   // symbol.
 912   // The symbol flag is also used to tag memory load events by adding 3 to the
 913   // base values, i.e. 3 not a symbol, 4 global symbol and 5 local symbol.
 914   if (!ExpectMemLoc && ParsingBuf[0] != '0' && ParsingBuf[0] != '1' &&
 915       ParsingBuf[0] != '2') {
 916     reportError("expected 0, 1 or 2");
 917     return make_error_code(llvm::errc::io_error);
 918   }
 919
 920   if (ExpectMemLoc && ParsingBuf[0] != '3' && ParsingBuf[0] != '4' &&
 921       ParsingBuf[0] != '5') {
 922     reportError("expected 3, 4 or 5");
 923     return make_error_code(llvm::errc::io_error);
 924   }
 925
 926   bool IsSymbol =
 927       (!ExpectMemLoc && (ParsingBuf[0] == '1' || ParsingBuf[0] == '2')) ||
 928       (ExpectMemLoc && (ParsingBuf[0] == '4' || ParsingBuf[0] == '5'));
 929   ParsingBuf = ParsingBuf.drop_front(1);
 930   Col += 1;
 931
 932   if (!expectAndConsumeFS())
 933     return make_error_code(llvm::errc::io_error);
 934   consumeAllRemainingFS();
 935
 936   // Read the string containing the symbol or the DSO name
 937   ErrorOr<StringRef> NameRes = parseString(FieldSeparator);
 938   if (std::error_code EC = NameRes.getError())
 939     return EC;
 940   StringRef Name = NameRes.get();
 941   consumeAllRemainingFS();
 942
 943   // Read the offset
 944   ErrorOr<uint64_t> Offset = parseHexField(EndChar, EndNl);
 945   if (std::error_code EC = Offset.getError())
 946     return EC;
 947
 948   return Location(IsSymbol, Name, Offset.get());
 949 }
 950
 951 ErrorOr<BranchInfo> DataReader::parseBranchInfo() {
 952   ErrorOr<Location> Res = parseLocation(FieldSeparator);
 953   if (std::error_code EC = Res.getError())
 954     return EC;
 955   Location From = Res.get();
 956
 957   consumeAllRemainingFS();
 958   Res = parseLocation(FieldSeparator);
 959   if (std::error_code EC = Res.getError())
 960     return EC;
 961   Location To = Res.get();
 962
 963   consumeAllRemainingFS();
 964   ErrorOr<int64_t> MRes = parseNumberField(FieldSeparator);
 965   if (std::error_code EC = MRes.getError())
 966     return EC;
 967   int64_t NumMispreds = MRes.get();
 968
 969   consumeAllRemainingFS();
 970   ErrorOr<int64_t> BRes = parseNumberField(FieldSeparator, /* EndNl = */ true);
 971   if (std::error_code EC = BRes.getError())
 972     return EC;
 973   int64_t NumBranches = BRes.get();
 974
 975   consumeAllRemainingFS();
 976   if (!checkAndConsumeNewLine()) {
 977     reportError("expected end of line");
 978     return make_error_code(llvm::errc::io_error);
 979   }
 980
 981   return BranchInfo(std::move(From), std::move(To), NumMispreds, NumBranches);
 982 }
 983
 984 ErrorOr<MemInfo> DataReader::parseMemInfo() {
 985   ErrorOr<Location> Res = parseMemLocation(FieldSeparator);
 986   if (std::error_code EC = Res.getError())
 987     return EC;
 988   Location Offset = Res.get();
 989
 990   consumeAllRemainingFS();
 991   Res = parseMemLocation(FieldSeparator);
 992   if (std::error_code EC = Res.getError())
 993     return EC;
 994   Location Addr = Res.get();
 995
 996   consumeAllRemainingFS();
 997   ErrorOr<int64_t> CountRes = parseNumberField(FieldSeparator, true);
 998   if (std::error_code EC = CountRes.getError())
 999     return EC;
1000
1001   consumeAllRemainingFS();
1002   if (!checkAndConsumeNewLine()) {
1003     reportError("expected end of line");
1004     return make_error_code(llvm::errc::io_error);
1005   }
1006
1007   return MemInfo(Offset, Addr, CountRes.get());
1008 }
1009
1010 ErrorOr<SampleInfo> DataReader::parseSampleInfo() {
1011   ErrorOr<Location> Res = parseLocation(FieldSeparator);
1012   if (std::error_code EC = Res.getError())
1013     return EC;
1014   Location Address = Res.get();
1015
1016   consumeAllRemainingFS();
1017   ErrorOr<int64_t> BRes = parseNumberField(FieldSeparator, /* EndNl = */ true);
1018   if (std::error_code EC = BRes.getError())
1019     return EC;
1020   int64_t Occurrences = BRes.get();
1021
1022   consumeAllRemainingFS();
1023   if (!checkAndConsumeNewLine()) {
1024     reportError("expected end of line");
1025     return make_error_code(llvm::errc::io_error);
1026   }
1027
1028   return SampleInfo(std::move(Address), Occurrences);
1029 }
1030
1031 ErrorOr<bool> DataReader::maybeParseNoLBRFlag() {
1032   if (ParsingBuf.size() < 6 || ParsingBuf.substr(0, 6) != "no_lbr")
1033     return false;
1034   ParsingBuf = ParsingBuf.drop_front(6);
1035   Col += 6;
1036
1037   if (ParsingBuf.size() > 0 && ParsingBuf[0] == ' ')
1038     ParsingBuf = ParsingBuf.drop_front(1);
1039
1040   while (ParsingBuf.size() > 0 && ParsingBuf[0] != '\n') {
1041     ErrorOr<StringRef> EventName = parseString(' ', true);
1042     if (!EventName)
1043       return make_error_code(llvm::errc::io_error);
1044     EventNames.insert(EventName.get());
1045   }
1046
1047   if (!checkAndConsumeNewLine()) {
1048     reportError("malformed no_lbr line");
1049     return make_error_code(llvm::errc::io_error);
1050   }
1051   return true;
1052 }
1053
1054 ErrorOr<bool> DataReader::maybeParseBATFlag() {
1055   if (ParsingBuf.size() < 16 || ParsingBuf.substr(0, 16) != "boltedcollection")
1056     return false;
1057   ParsingBuf = ParsingBuf.drop_front(16);
1058   Col += 16;
1059
1060   if (!checkAndConsumeNewLine()) {
1061     reportError("malformed boltedcollection line");
1062     return make_error_code(llvm::errc::io_error);
1063   }
1064   return true;
1065 }
1066
1067 bool DataReader::hasBranchData() {
1068   if (ParsingBuf.size() == 0)
1069     return false;
1070
1071   if (ParsingBuf[0] == '0' || ParsingBuf[0] == '1' || ParsingBuf[0] == '2')
1072     return true;
1073   return false;
1074 }
1075
1076 bool DataReader::hasMemData() {
1077   if (ParsingBuf.size() == 0)
1078     return false;
1079
1080   if (ParsingBuf[0] == '3' || ParsingBuf[0] == '4' || ParsingBuf[0] == '5')
1081     return true;
1082   return false;
1083 }
1084
1085 std::error_code DataReader::parseInNoLBRMode() {
1086   auto GetOrCreateFuncEntry = [&](StringRef Name) {
1087     auto I = NamesToSamples.find(Name);
1088     if (I == NamesToSamples.end()) {
1089       bool Success;
1090       std::tie(I, Success) = NamesToSamples.insert(std::make_pair(
1091           Name, FuncSampleData(Name, FuncSampleData::ContainerTy())));
1092
1093       assert(Success && "unexpected result of insert");
1094     }
1095     return I;
1096   };
1097
1098   auto GetOrCreateFuncMemEntry = [&](StringRef Name) {
1099     auto I = NamesToMemEvents.find(Name);
1100     if (I == NamesToMemEvents.end()) {
1101       bool Success;
1102       std::tie(I, Success) = NamesToMemEvents.insert(
1103           std::make_pair(Name, FuncMemData(Name, FuncMemData::ContainerTy())));
1104       assert(Success && "unexpected result of insert");
1105     }
1106     return I;
1107   };
1108
1109   while (hasBranchData()) {
1110     ErrorOr<SampleInfo> Res = parseSampleInfo();
1111     if (std::error_code EC = Res.getError())
1112       return EC;
1113
1114     SampleInfo SI = Res.get();
1115
1116     // Ignore samples not involving known locations
1117     if (!SI.Loc.IsSymbol)
1118       continue;
1119
1120     auto I = GetOrCreateFuncEntry(SI.Loc.Name);
1121     I->second.Data.emplace_back(std::move(SI));
1122   }
1123
1124   while (hasMemData()) {
1125     ErrorOr<MemInfo> Res = parseMemInfo();
1126     if (std::error_code EC = Res.getError())
1127       return EC;
1128
1129     MemInfo MI = Res.get();
1130
1131     // Ignore memory events not involving known pc.
1132     if (!MI.Offset.IsSymbol)
1133       continue;
1134
1135     auto I = GetOrCreateFuncMemEntry(MI.Offset.Name);
1136     I->second.Data.emplace_back(std::move(MI));
1137   }
1138
1139   for (auto &FuncSamples : NamesToSamples)
1140     llvm::stable_sort(FuncSamples.second.Data);
1141
1142   for (auto &MemEvents : NamesToMemEvents)
1143     llvm::stable_sort(MemEvents.second.Data);
1144
1145   return std::error_code();
1146 }
1147
1148 std::error_code DataReader::parse() {
1149   auto GetOrCreateFuncEntry = [&](StringRef Name) {
1150     auto I = NamesToBranches.find(Name);
1151     if (I == NamesToBranches.end()) {
1152       bool Success;
1153       std::tie(I, Success) = NamesToBranches.insert(std::make_pair(
1154           Name, FuncBranchData(Name, FuncBranchData::ContainerTy(),
1155                                FuncBranchData::ContainerTy())));
1156       assert(Success && "unexpected result of insert");
1157     }
1158     return I;
1159   };
1160
1161   auto GetOrCreateFuncMemEntry = [&](StringRef Name) {
1162     auto I = NamesToMemEvents.find(Name);
1163     if (I == NamesToMemEvents.end()) {
1164       bool Success;
1165       std::tie(I, Success) = NamesToMemEvents.insert(
1166           std::make_pair(Name, FuncMemData(Name, FuncMemData::ContainerTy())));
1167       assert(Success && "unexpected result of insert");
1168     }
1169     return I;
1170   };
1171
1172   Col = 0;
1173   Line = 1;
1174   ErrorOr<bool> FlagOrErr = maybeParseNoLBRFlag();
1175   if (!FlagOrErr)
1176     return FlagOrErr.getError();
1177   NoLBRMode = *FlagOrErr;
1178
1179   ErrorOr<bool> BATFlagOrErr = maybeParseBATFlag();
1180   if (!BATFlagOrErr)
1181     return BATFlagOrErr.getError();
1182   BATMode = *BATFlagOrErr;
1183
1184   if (!hasBranchData() && !hasMemData()) {
1185     Diag << "ERROR: no valid profile data found\n";
1186     return make_error_code(llvm::errc::io_error);
1187   }
1188
1189   if (NoLBRMode)
1190     return parseInNoLBRMode();
1191
1192   while (hasBranchData()) {
1193     ErrorOr<BranchInfo> Res = parseBranchInfo();
1194     if (std::error_code EC = Res.getError())
1195       return EC;
1196
1197     BranchInfo BI = Res.get();
1198
1199     // Ignore branches not involving known location.
1200     if (!BI.From.IsSymbol && !BI.To.IsSymbol)
1201       continue;
1202
1203     auto I = GetOrCreateFuncEntry(BI.From.Name);
1204     I->second.Data.emplace_back(std::move(BI));
1205
1206     // Add entry data for branches to another function or branches
1207     // to entry points (including recursive calls)
1208     if (BI.To.IsSymbol &&
1209         (!BI.From.Name.equals(BI.To.Name) || BI.To.Offset == 0)) {
1210       I = GetOrCreateFuncEntry(BI.To.Name);
1211       I->second.EntryData.emplace_back(std::move(BI));
1212     }
1213
1214     // If destination is the function start - update execution count.
1215     // NB: the data is skewed since we cannot tell tail recursion from
1216     //     branches to the function start.
1217     if (BI.To.IsSymbol && BI.To.Offset == 0) {
1218       I = GetOrCreateFuncEntry(BI.To.Name);
1219       I->second.ExecutionCount += BI.Branches;
1220     }
1221   }
1222
1223   while (hasMemData()) {
1224     ErrorOr<MemInfo> Res = parseMemInfo();
1225     if (std::error_code EC = Res.getError())
1226       return EC;
1227
1228     MemInfo MI = Res.get();
1229
1230     // Ignore memory events not involving known pc.
1231     if (!MI.Offset.IsSymbol)
1232       continue;
1233
1234     auto I = GetOrCreateFuncMemEntry(MI.Offset.Name);
1235     I->second.Data.emplace_back(std::move(MI));
1236   }
1237
1238   for (auto &FuncBranches : NamesToBranches)
1239     llvm::stable_sort(FuncBranches.second.Data);
1240
1241   for (auto &MemEvents : NamesToMemEvents)
1242     llvm::stable_sort(MemEvents.second.Data);
1243
1244   return std::error_code();
1245 }
1246
1247 void DataReader::buildLTONameMaps() {
1248   for (auto &FuncData : NamesToBranches) {
1249     const StringRef FuncName = FuncData.first;
1250     const std::optional<StringRef> CommonName = getLTOCommonName(FuncName);
1251     if (CommonName)
1252       LTOCommonNameMap[*CommonName].push_back(&FuncData.second);
1253   }
1254
1255   for (auto &FuncData : NamesToMemEvents) {
1256     const StringRef FuncName = FuncData.first;
1257     const std::optional<StringRef> CommonName = getLTOCommonName(FuncName);
1258     if (CommonName)
1259       LTOCommonNameMemMap[*CommonName].push_back(&FuncData.second);
1260   }
1261 }
1262
1263 template <typename MapTy>
1264 static typename MapTy::mapped_type *
1265 fetchMapEntry(MapTy &Map, const std::vector<MCSymbol *> &Symbols) {
1266   // Do a reverse order iteration since the name in profile has a higher chance
1267   // of matching a name at the end of the list.
1268   for (const MCSymbol *Symbol : llvm::reverse(Symbols)) {
1269     auto I = Map.find(normalizeName(Symbol->getName()));
1270     if (I != Map.end())
1271       return &I->second;
1272   }
1273   return nullptr;
1274 }
1275
1276 template <typename MapTy>
1277 static typename MapTy::mapped_type *
1278 fetchMapEntry(MapTy &Map, const std::vector<StringRef> &FuncNames) {
1279   // Do a reverse order iteration since the name in profile has a higher chance
1280   // of matching a name at the end of the list.
1281   for (StringRef Name : llvm::reverse(FuncNames)) {
1282     auto I = Map.find(normalizeName(Name));
1283     if (I != Map.end())
1284       return &I->second;
1285   }
1286   return nullptr;
1287 }
1288
1289 template <typename MapTy>
1290 static std::vector<typename MapTy::mapped_type *>
1291 fetchMapEntriesRegex(MapTy &Map,
1292                      const StringMap<std::vector<typename MapTy::mapped_type *>>
1293                          &LTOCommonNameMap,
1294                      const std::vector<StringRef> &FuncNames) {
1295   std::vector<typename MapTy::mapped_type *> AllData;
1296   // Do a reverse order iteration since the name in profile has a higher chance
1297   // of matching a name at the end of the list.
1298   for (StringRef FuncName : llvm::reverse(FuncNames)) {
1299     std::string Name = normalizeName(FuncName);
1300     const std::optional<StringRef> LTOCommonName = getLTOCommonName(Name);
1301     if (LTOCommonName) {
1302       auto I = LTOCommonNameMap.find(*LTOCommonName);
1303       if (I != LTOCommonNameMap.end()) {
1304         const std::vector<typename MapTy::mapped_type *> &CommonData =
1305             I->second;
1306         AllData.insert(AllData.end(), CommonData.begin(), CommonData.end());
1307       }
1308     } else {
1309       auto I = Map.find(Name);
1310       if (I != Map.end())
1311         return {&I->second};
1312     }
1313   }
1314   return AllData;
1315 }
1316
1317 bool DataReader::mayHaveProfileData(const BinaryFunction &Function) {
1318   if (getBranchData(Function) || getMemData(Function))
1319     return true;
1320
1321   if (getFuncSampleData(Function.getNames()) ||
1322       getBranchDataForNames(Function.getNames()) ||
1323       getMemDataForNames(Function.getNames()))
1324     return true;
1325
1326   if (!hasVolatileName(Function))
1327     return false;
1328
1329   const std::vector<FuncBranchData *> AllBranchData =
1330       getBranchDataForNamesRegex(Function.getNames());
1331   if (!AllBranchData.empty())
1332     return true;
1333
1334   const std::vector<FuncMemData *> AllMemData =
1335       getMemDataForNamesRegex(Function.getNames());
1336   if (!AllMemData.empty())
1337     return true;
1338
1339   return false;
1340 }
1341
1342 FuncBranchData *
1343 DataReader::getBranchDataForNames(const std::vector<StringRef> &FuncNames) {
1344   return fetchMapEntry<NamesToBranchesMapTy>(NamesToBranches, FuncNames);
1345 }
1346
1347 FuncBranchData *
1348 DataReader::getBranchDataForSymbols(const std::vector<MCSymbol *> &Symbols) {
1349   return fetchMapEntry<NamesToBranchesMapTy>(NamesToBranches, Symbols);
1350 }
1351
1352 FuncMemData *
1353 DataReader::getMemDataForNames(const std::vector<StringRef> &FuncNames) {
1354   return fetchMapEntry<NamesToMemEventsMapTy>(NamesToMemEvents, FuncNames);
1355 }
1356
1357 FuncSampleData *
1358 DataReader::getFuncSampleData(const std::vector<StringRef> &FuncNames) {
1359   return fetchMapEntry<NamesToSamplesMapTy>(NamesToSamples, FuncNames);
1360 }
1361
1362 std::vector<FuncBranchData *> DataReader::getBranchDataForNamesRegex(
1363     const std::vector<StringRef> &FuncNames) {
1364   return fetchMapEntriesRegex(NamesToBranches, LTOCommonNameMap, FuncNames);
1365 }
1366
1367 std::vector<FuncMemData *>
1368 DataReader::getMemDataForNamesRegex(const std::vector<StringRef> &FuncNames) {
1369   return fetchMapEntriesRegex(NamesToMemEvents, LTOCommonNameMemMap, FuncNames);
1370 }
1371
1372 bool DataReader::hasLocalsWithFileName() const {
1373   for (const auto &Func : NamesToBranches) {
1374     const StringRef &FuncName = Func.first;
1375     if (FuncName.count('/') == 2 && FuncName[0] != '/')
1376       return true;
1377   }
1378   return false;
1379 }
1380
1381 void DataReader::dump() const {
1382   for (const auto &KV : NamesToBranches) {
1383     const StringRef Name = KV.first;
1384     const FuncBranchData &FBD = KV.second;
1385     Diag << Name << " branches:\n";
1386     for (const BranchInfo &BI : FBD.Data)
1387       Diag << BI.From.Name << " " << BI.From.Offset << " " << BI.To.Name << " "
1388            << BI.To.Offset << " " << BI.Mispreds << " " << BI.Branches << "\n";
1389     Diag << Name << " entry points:\n";
1390     for (const BranchInfo &BI : FBD.EntryData)
1391       Diag << BI.From.Name << " " << BI.From.Offset << " " << BI.To.Name << " "
1392            << BI.To.Offset << " " << BI.Mispreds << " " << BI.Branches << "\n";
1393   }
1394
1395   for (auto I = EventNames.begin(), E = EventNames.end(); I != E; ++I) {
1396     StringRef Event = I->getKey();
1397     Diag << "Data was collected with event: " << Event << "\n";
1398   }
1399   for (const auto &KV : NamesToSamples) {
1400     const StringRef Name = KV.first;
1401     const FuncSampleData &FSD = KV.second;
1402     Diag << Name << " samples:\n";
1403     for (const SampleInfo &SI : FSD.Data)
1404       Diag << SI.Loc.Name << " " << SI.Loc.Offset << " " << SI.Hits << "\n";
1405   }
1406
1407   for (const auto &KV : NamesToMemEvents) {
1408     const StringRef Name = KV.first;
1409     const FuncMemData &FMD = KV.second;
1410     Diag << "Memory events for " << Name;
1411     Location LastOffset(0);
1412     for (const MemInfo &MI : FMD.Data) {
1413       if (MI.Offset == LastOffset)
1414         Diag << ", " << MI.Addr << "/" << MI.Count;
1415       else
1416         Diag << "\n" << MI.Offset << ": " << MI.Addr << "/" << MI.Count;
1417       LastOffset = MI.Offset;
1418     }
1419     Diag << "\n";
1420   }
1421 }
1422
1423 } // namespace bolt
1424 } // namespace llvm