llvm/tools/llvm-profgen/ProfiledBinary.cpp

   1 //===-- ProfiledBinary.cpp - Binary decoder ---------------------*- C++ -*-===//
   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 "ProfiledBinary.h"
  10 #include "ErrorHandling.h"
  11 #include "MissingFrameInferrer.h"
  12 #include "ProfileGenerator.h"
  13 #include "llvm/DebugInfo/Symbolize/SymbolizableModule.h"
  14 #include "llvm/Demangle/Demangle.h"
  15 #include "llvm/IR/DebugInfoMetadata.h"
  16 #include "llvm/MC/TargetRegistry.h"
  17 #include "llvm/Support/CommandLine.h"
  18 #include "llvm/Support/Debug.h"
  19 #include "llvm/Support/Format.h"
  20 #include "llvm/Support/TargetSelect.h"
  21 #include "llvm/TargetParser/Triple.h"
  22 #include <optional>
  23
  24 #define DEBUG_TYPE "load-binary"
  25
  26 using namespace llvm;
  27 using namespace sampleprof;
  28
  29 cl::opt<bool> ShowDisassemblyOnly("show-disassembly-only",
  30                                   cl::desc("Print disassembled code."));
  31
  32 cl::opt<bool> ShowSourceLocations("show-source-locations",
  33                                   cl::desc("Print source locations."));
  34
  35 static cl::opt<bool>
  36     ShowCanonicalFnName("show-canonical-fname",
  37                         cl::desc("Print canonical function name."));
  38
  39 static cl::opt<bool> ShowPseudoProbe(
  40     "show-pseudo-probe",
  41     cl::desc("Print pseudo probe section and disassembled info."));
  42
  43 static cl::opt<bool> UseDwarfCorrelation(
  44     "use-dwarf-correlation",
  45     cl::desc("Use dwarf for profile correlation even when binary contains "
  46              "pseudo probe."));
  47
  48 static cl::opt<std::string>
  49     DWPPath("dwp", cl::init(""),
  50             cl::desc("Path of .dwp file. When not specified, it will be "
  51                      "<binary>.dwp in the same directory as the main binary."));
  52
  53 static cl::list<std::string> DisassembleFunctions(
  54     "disassemble-functions", cl::CommaSeparated,
  55     cl::desc("List of functions to print disassembly for. Accept demangled "
  56              "names only. Only work with show-disassembly-only"));
  57
  58 extern cl::opt<bool> ShowDetailedWarning;
  59 extern cl::opt<bool> InferMissingFrames;
  60
  61 namespace llvm {
  62 namespace sampleprof {
  63
  64 static const Target *getTarget(const ObjectFile *Obj) {
  65   Triple TheTriple = Obj->makeTriple();
  66   std::string Error;
  67   std::string ArchName;
  68   const Target *TheTarget =
  69       TargetRegistry::lookupTarget(ArchName, TheTriple, Error);
  70   if (!TheTarget)
  71     exitWithError(Error, Obj->getFileName());
  72   return TheTarget;
  73 }
  74
  75 void BinarySizeContextTracker::addInstructionForContext(
  76     const SampleContextFrameVector &Context, uint32_t InstrSize) {
  77   ContextTrieNode *CurNode = &RootContext;
  78   bool IsLeaf = true;
  79   for (const auto &Callsite : reverse(Context)) {
  80     FunctionId CallerName = Callsite.Func;
  81     LineLocation CallsiteLoc = IsLeaf ? LineLocation(0, 0) : Callsite.Location;
  82     CurNode = CurNode->getOrCreateChildContext(CallsiteLoc, CallerName);
  83     IsLeaf = false;
  84   }
  85
  86   CurNode->addFunctionSize(InstrSize);
  87 }
  88
  89 uint32_t
  90 BinarySizeContextTracker::getFuncSizeForContext(const ContextTrieNode *Node) {
  91   ContextTrieNode *CurrNode = &RootContext;
  92   ContextTrieNode *PrevNode = nullptr;
  93
  94   std::optional<uint32_t> Size;
  95
  96   // Start from top-level context-less function, traverse down the reverse
  97   // context trie to find the best/longest match for given context, then
  98   // retrieve the size.
  99   LineLocation CallSiteLoc(0, 0);
 100   while (CurrNode && Node->getParentContext() != nullptr) {
 101     PrevNode = CurrNode;
 102     CurrNode = CurrNode->getChildContext(CallSiteLoc, Node->getFuncName());
 103     if (CurrNode && CurrNode->getFunctionSize())
 104       Size = *CurrNode->getFunctionSize();
 105     CallSiteLoc = Node->getCallSiteLoc();
 106     Node = Node->getParentContext();
 107   }
 108
 109   // If we traversed all nodes along the path of the context and haven't
 110   // found a size yet, pivot to look for size from sibling nodes, i.e size
 111   // of inlinee under different context.
 112   if (!Size) {
 113     if (!CurrNode)
 114       CurrNode = PrevNode;
 115     while (!Size && CurrNode && !CurrNode->getAllChildContext().empty()) {
 116       CurrNode = &CurrNode->getAllChildContext().begin()->second;
 117       if (CurrNode->getFunctionSize())
 118         Size = *CurrNode->getFunctionSize();
 119     }
 120   }
 121
 122   assert(Size && "We should at least find one context size.");
 123   return *Size;
 124 }
 125
 126 void BinarySizeContextTracker::trackInlineesOptimizedAway(
 127     MCPseudoProbeDecoder &ProbeDecoder) {
 128   ProbeFrameStack ProbeContext;
 129   for (const auto &Child : ProbeDecoder.getDummyInlineRoot().getChildren())
 130     trackInlineesOptimizedAway(ProbeDecoder, *Child.second.get(), ProbeContext);
 131 }
 132
 133 void BinarySizeContextTracker::trackInlineesOptimizedAway(
 134     MCPseudoProbeDecoder &ProbeDecoder,
 135     MCDecodedPseudoProbeInlineTree &ProbeNode, ProbeFrameStack &ProbeContext) {
 136   StringRef FuncName =
 137       ProbeDecoder.getFuncDescForGUID(ProbeNode.Guid)->FuncName;
 138   ProbeContext.emplace_back(FuncName, 0);
 139
 140   // This ProbeContext has a probe, so it has code before inlining and
 141   // optimization. Make sure we mark its size as known.
 142   if (!ProbeNode.getProbes().empty()) {
 143     ContextTrieNode *SizeContext = &RootContext;
 144     for (auto &ProbeFrame : reverse(ProbeContext)) {
 145       StringRef CallerName = ProbeFrame.first;
 146       LineLocation CallsiteLoc(ProbeFrame.second, 0);
 147       SizeContext =
 148           SizeContext->getOrCreateChildContext(CallsiteLoc,
 149                                                FunctionId(CallerName));
 150     }
 151     // Add 0 size to make known.
 152     SizeContext->addFunctionSize(0);
 153   }
 154
 155   // DFS down the probe inline tree
 156   for (const auto &ChildNode : ProbeNode.getChildren()) {
 157     InlineSite Location = ChildNode.first;
 158     ProbeContext.back().second = std::get<1>(Location);
 159     trackInlineesOptimizedAway(ProbeDecoder, *ChildNode.second.get(),
 160                                ProbeContext);
 161   }
 162
 163   ProbeContext.pop_back();
 164 }
 165
 166 ProfiledBinary::ProfiledBinary(const StringRef ExeBinPath,
 167                                const StringRef DebugBinPath)
 168     : Path(ExeBinPath), DebugBinaryPath(DebugBinPath),
 169       SymbolizerOpts(getSymbolizerOpts()), ProEpilogTracker(this),
 170       Symbolizer(std::make_unique<symbolize::LLVMSymbolizer>(SymbolizerOpts)),
 171       TrackFuncContextSize(EnableCSPreInliner && UseContextCostForPreInliner) {
 172   // Point to executable binary if debug info binary is not specified.
 173   SymbolizerPath = DebugBinPath.empty() ? ExeBinPath : DebugBinPath;
 174   if (InferMissingFrames)
 175     MissingContextInferrer = std::make_unique<MissingFrameInferrer>(this);
 176   load();
 177 }
 178
 179 ProfiledBinary::~ProfiledBinary() {}
 180
 181 void ProfiledBinary::warnNoFuncEntry() {
 182   uint64_t NoFuncEntryNum = 0;
 183   for (auto &F : BinaryFunctions) {
 184     if (F.second.Ranges.empty())
 185       continue;
 186     bool hasFuncEntry = false;
 187     for (auto &R : F.second.Ranges) {
 188       if (FuncRange *FR = findFuncRangeForStartAddr(R.first)) {
 189         if (FR->IsFuncEntry) {
 190           hasFuncEntry = true;
 191           break;
 192         }
 193       }
 194     }
 195
 196     if (!hasFuncEntry) {
 197       NoFuncEntryNum++;
 198       if (ShowDetailedWarning)
 199         WithColor::warning()
 200             << "Failed to determine function entry for " << F.first
 201             << " due to inconsistent name from symbol table and dwarf info.\n";
 202     }
 203   }
 204   emitWarningSummary(NoFuncEntryNum, BinaryFunctions.size(),
 205                      "of functions failed to determine function entry due to "
 206                      "inconsistent name from symbol table and dwarf info.");
 207 }
 208
 209 void ProfiledBinary::load() {
 210   // Attempt to open the binary.
 211   OwningBinary<Binary> OBinary = unwrapOrError(createBinary(Path), Path);
 212   Binary &ExeBinary = *OBinary.getBinary();
 213
 214   auto *Obj = dyn_cast<ELFObjectFileBase>(&ExeBinary);
 215   if (!Obj)
 216     exitWithError("not a valid Elf image", Path);
 217
 218   TheTriple = Obj->makeTriple();
 219
 220   LLVM_DEBUG(dbgs() << "Loading " << Path << "\n");
 221
 222   // Find the preferred load address for text sections.
 223   setPreferredTextSegmentAddresses(Obj);
 224
 225   // Load debug info of subprograms from DWARF section.
 226   // If path of debug info binary is specified, use the debug info from it,
 227   // otherwise use the debug info from the executable binary.
 228   if (!DebugBinaryPath.empty()) {
 229     OwningBinary<Binary> DebugPath =
 230         unwrapOrError(createBinary(DebugBinaryPath), DebugBinaryPath);
 231     loadSymbolsFromDWARF(*cast<ObjectFile>(DebugPath.getBinary()));
 232   } else {
 233     loadSymbolsFromDWARF(*cast<ObjectFile>(&ExeBinary));
 234   }
 235
 236   DisassembleFunctionSet.insert(DisassembleFunctions.begin(),
 237                                 DisassembleFunctions.end());
 238
 239   checkPseudoProbe(Obj);
 240
 241   if (UsePseudoProbes)
 242     populateElfSymbolAddressList(Obj);
 243
 244   if (ShowDisassemblyOnly)
 245     decodePseudoProbe(Obj);
 246
 247   // Disassemble the text sections.
 248   disassemble(Obj);
 249
 250   // Use function start and return address to infer prolog and epilog
 251   ProEpilogTracker.inferPrologAddresses(StartAddrToFuncRangeMap);
 252   ProEpilogTracker.inferEpilogAddresses(RetAddressSet);
 253
 254   warnNoFuncEntry();
 255
 256   // TODO: decode other sections.
 257 }
 258
 259 bool ProfiledBinary::inlineContextEqual(uint64_t Address1, uint64_t Address2) {
 260   const SampleContextFrameVector &Context1 =
 261       getCachedFrameLocationStack(Address1);
 262   const SampleContextFrameVector &Context2 =
 263       getCachedFrameLocationStack(Address2);
 264   if (Context1.size() != Context2.size())
 265     return false;
 266   if (Context1.empty())
 267     return false;
 268   // The leaf frame contains location within the leaf, and it
 269   // needs to be remove that as it's not part of the calling context
 270   return std::equal(Context1.begin(), Context1.begin() + Context1.size() - 1,
 271                     Context2.begin(), Context2.begin() + Context2.size() - 1);
 272 }
 273
 274 SampleContextFrameVector
 275 ProfiledBinary::getExpandedContext(const SmallVectorImpl<uint64_t> &Stack,
 276                                    bool &WasLeafInlined) {
 277   SampleContextFrameVector ContextVec;
 278   if (Stack.empty())
 279     return ContextVec;
 280   // Process from frame root to leaf
 281   for (auto Address : Stack) {
 282     const SampleContextFrameVector &ExpandedContext =
 283         getCachedFrameLocationStack(Address);
 284     // An instruction without a valid debug line will be ignored by sample
 285     // processing
 286     if (ExpandedContext.empty())
 287       return SampleContextFrameVector();
 288     // Set WasLeafInlined to the size of inlined frame count for the last
 289     // address which is leaf
 290     WasLeafInlined = (ExpandedContext.size() > 1);
 291     ContextVec.append(ExpandedContext);
 292   }
 293
 294   // Replace with decoded base discriminator
 295   for (auto &Frame : ContextVec) {
 296     Frame.Location.Discriminator = ProfileGeneratorBase::getBaseDiscriminator(
 297         Frame.Location.Discriminator, UseFSDiscriminator);
 298   }
 299
 300   assert(ContextVec.size() && "Context length should be at least 1");
 301
 302   // Compress the context string except for the leaf frame
 303   auto LeafFrame = ContextVec.back();
 304   LeafFrame.Location = LineLocation(0, 0);
 305   ContextVec.pop_back();
 306   CSProfileGenerator::compressRecursionContext(ContextVec);
 307   CSProfileGenerator::trimContext(ContextVec);
 308   ContextVec.push_back(LeafFrame);
 309   return ContextVec;
 310 }
 311
 312 template <class ELFT>
 313 void ProfiledBinary::setPreferredTextSegmentAddresses(const ELFFile<ELFT> &Obj,
 314                                                       StringRef FileName) {
 315   const auto &PhdrRange = unwrapOrError(Obj.program_headers(), FileName);
 316   // FIXME: This should be the page size of the system running profiling.
 317   // However such info isn't available at post-processing time, assuming
 318   // 4K page now. Note that we don't use EXEC_PAGESIZE from <linux/param.h>
 319   // because we may build the tools on non-linux.
 320   uint32_t PageSize = 0x1000;
 321   for (const typename ELFT::Phdr &Phdr : PhdrRange) {
 322     if (Phdr.p_type == ELF::PT_LOAD) {
 323       if (!FirstLoadableAddress)
 324         FirstLoadableAddress = Phdr.p_vaddr & ~(PageSize - 1U);
 325       if (Phdr.p_flags & ELF::PF_X) {
 326         // Segments will always be loaded at a page boundary.
 327         PreferredTextSegmentAddresses.push_back(Phdr.p_vaddr &
 328                                                 ~(PageSize - 1U));
 329         TextSegmentOffsets.push_back(Phdr.p_offset & ~(PageSize - 1U));
 330       }
 331     }
 332   }
 333
 334   if (PreferredTextSegmentAddresses.empty())
 335     exitWithError("no executable segment found", FileName);
 336 }
 337
 338 void ProfiledBinary::setPreferredTextSegmentAddresses(
 339     const ELFObjectFileBase *Obj) {
 340   if (const auto *ELFObj = dyn_cast<ELF32LEObjectFile>(Obj))
 341     setPreferredTextSegmentAddresses(ELFObj->getELFFile(), Obj->getFileName());
 342   else if (const auto *ELFObj = dyn_cast<ELF32BEObjectFile>(Obj))
 343     setPreferredTextSegmentAddresses(ELFObj->getELFFile(), Obj->getFileName());
 344   else if (const auto *ELFObj = dyn_cast<ELF64LEObjectFile>(Obj))
 345     setPreferredTextSegmentAddresses(ELFObj->getELFFile(), Obj->getFileName());
 346   else if (const auto *ELFObj = cast<ELF64BEObjectFile>(Obj))
 347     setPreferredTextSegmentAddresses(ELFObj->getELFFile(), Obj->getFileName());
 348   else
 349     llvm_unreachable("invalid ELF object format");
 350 }
 351
 352 void ProfiledBinary::checkPseudoProbe(const ELFObjectFileBase *Obj) {
 353   if (UseDwarfCorrelation)
 354     return;
 355
 356   bool HasProbeDescSection = false;
 357   bool HasPseudoProbeSection = false;
 358
 359   StringRef FileName = Obj->getFileName();
 360   for (section_iterator SI = Obj->section_begin(), SE = Obj->section_end();
 361        SI != SE; ++SI) {
 362     const SectionRef &Section = *SI;
 363     StringRef SectionName = unwrapOrError(Section.getName(), FileName);
 364     if (SectionName == ".pseudo_probe_desc") {
 365       HasProbeDescSection = true;
 366     } else if (SectionName == ".pseudo_probe") {
 367       HasPseudoProbeSection = true;
 368     }
 369   }
 370
 371   // set UsePseudoProbes flag, used for PerfReader
 372   UsePseudoProbes = HasProbeDescSection && HasPseudoProbeSection;
 373 }
 374
 375 void ProfiledBinary::decodePseudoProbe(const ELFObjectFileBase *Obj) {
 376   if (!UsePseudoProbes)
 377     return;
 378
 379   MCPseudoProbeDecoder::Uint64Set GuidFilter;
 380   MCPseudoProbeDecoder::Uint64Map FuncStartAddresses;
 381   if (ShowDisassemblyOnly) {
 382     if (DisassembleFunctionSet.empty()) {
 383       FuncStartAddresses = SymbolStartAddrs;
 384     } else {
 385       for (auto &F : DisassembleFunctionSet) {
 386         auto GUID = Function::getGUID(F.first());
 387         if (auto StartAddr = SymbolStartAddrs.lookup(GUID)) {
 388           FuncStartAddresses[GUID] = StartAddr;
 389           FuncRange &Range = StartAddrToFuncRangeMap[StartAddr];
 390           GuidFilter.insert(Function::getGUID(Range.getFuncName()));
 391         }
 392       }
 393     }
 394   } else {
 395     for (auto *F : ProfiledFunctions) {
 396       GuidFilter.insert(Function::getGUID(F->FuncName));
 397       for (auto &Range : F->Ranges) {
 398         auto GUIDs = StartAddrToSymMap.equal_range(Range.first);
 399         for (auto I = GUIDs.first; I != GUIDs.second; ++I)
 400           FuncStartAddresses[I->second] = I->first;
 401       }
 402     }
 403   }
 404
 405   StringRef FileName = Obj->getFileName();
 406   for (section_iterator SI = Obj->section_begin(), SE = Obj->section_end();
 407        SI != SE; ++SI) {
 408     const SectionRef &Section = *SI;
 409     StringRef SectionName = unwrapOrError(Section.getName(), FileName);
 410
 411     if (SectionName == ".pseudo_probe_desc") {
 412       StringRef Contents = unwrapOrError(Section.getContents(), FileName);
 413       if (!ProbeDecoder.buildGUID2FuncDescMap(
 414               reinterpret_cast<const uint8_t *>(Contents.data()),
 415               Contents.size()))
 416         exitWithError(
 417             "Pseudo Probe decoder fail in .pseudo_probe_desc section");
 418     } else if (SectionName == ".pseudo_probe") {
 419       StringRef Contents = unwrapOrError(Section.getContents(), FileName);
 420       if (!ProbeDecoder.buildAddress2ProbeMap(
 421               reinterpret_cast<const uint8_t *>(Contents.data()),
 422               Contents.size(), GuidFilter, FuncStartAddresses))
 423         exitWithError("Pseudo Probe decoder fail in .pseudo_probe section");
 424     }
 425   }
 426
 427   // Build TopLevelProbeFrameMap to track size for optimized inlinees when probe
 428   // is available
 429   if (TrackFuncContextSize) {
 430     for (const auto &Child : ProbeDecoder.getDummyInlineRoot().getChildren()) {
 431       auto *Frame = Child.second.get();
 432       StringRef FuncName =
 433           ProbeDecoder.getFuncDescForGUID(Frame->Guid)->FuncName;
 434       TopLevelProbeFrameMap[FuncName] = Frame;
 435     }
 436   }
 437
 438   if (ShowPseudoProbe)
 439     ProbeDecoder.printGUID2FuncDescMap(outs());
 440 }
 441
 442 void ProfiledBinary::decodePseudoProbe() {
 443   OwningBinary<Binary> OBinary = unwrapOrError(createBinary(Path), Path);
 444   Binary &ExeBinary = *OBinary.getBinary();
 445   auto *Obj = dyn_cast<ELFObjectFileBase>(&ExeBinary);
 446   decodePseudoProbe(Obj);
 447 }
 448
 449 void ProfiledBinary::setIsFuncEntry(FuncRange *FuncRange,
 450                                     StringRef RangeSymName) {
 451   // Skip external function symbol.
 452   if (!FuncRange)
 453     return;
 454
 455   // Set IsFuncEntry to ture if there is only one range in the function or the
 456   // RangeSymName from ELF is equal to its DWARF-based function name.
 457   if (FuncRange->Func->Ranges.size() == 1 ||
 458       (!FuncRange->IsFuncEntry && FuncRange->getFuncName() == RangeSymName))
 459     FuncRange->IsFuncEntry = true;
 460 }
 461
 462 bool ProfiledBinary::dissassembleSymbol(std::size_t SI, ArrayRef<uint8_t> Bytes,
 463                                         SectionSymbolsTy &Symbols,
 464                                         const SectionRef &Section) {
 465   std::size_t SE = Symbols.size();
 466   uint64_t SectionAddress = Section.getAddress();
 467   uint64_t SectSize = Section.getSize();
 468   uint64_t StartAddress = Symbols[SI].Addr;
 469   uint64_t NextStartAddress =
 470       (SI + 1 < SE) ? Symbols[SI + 1].Addr : SectionAddress + SectSize;
 471   FuncRange *FRange = findFuncRange(StartAddress);
 472   setIsFuncEntry(FRange, FunctionSamples::getCanonicalFnName(Symbols[SI].Name));
 473   StringRef SymbolName =
 474       ShowCanonicalFnName
 475           ? FunctionSamples::getCanonicalFnName(Symbols[SI].Name)
 476           : Symbols[SI].Name;
 477   bool ShowDisassembly =
 478       ShowDisassemblyOnly && (DisassembleFunctionSet.empty() ||
 479                               DisassembleFunctionSet.count(SymbolName));
 480   if (ShowDisassembly)
 481     outs() << '<' << SymbolName << ">:\n";
 482
 483   uint64_t Address = StartAddress;
 484   // Size of a consecutive invalid instruction range starting from Address -1
 485   // backwards.
 486   uint64_t InvalidInstLength = 0;
 487   while (Address < NextStartAddress) {
 488     MCInst Inst;
 489     uint64_t Size;
 490     // Disassemble an instruction.
 491     bool Disassembled = DisAsm->getInstruction(
 492         Inst, Size, Bytes.slice(Address - SectionAddress), Address, nulls());
 493     if (Size == 0)
 494       Size = 1;
 495
 496     if (ShowDisassembly) {
 497       if (ShowPseudoProbe) {
 498         ProbeDecoder.printProbeForAddress(outs(), Address);
 499       }
 500       outs() << format("%8" PRIx64 ":", Address);
 501       size_t Start = outs().tell();
 502       if (Disassembled)
 503         IPrinter->printInst(&Inst, Address + Size, "", *STI.get(), outs());
 504       else
 505         outs() << "\t<unknown>";
 506       if (ShowSourceLocations) {
 507         unsigned Cur = outs().tell() - Start;
 508         if (Cur < 40)
 509           outs().indent(40 - Cur);
 510         InstructionPointer IP(this, Address);
 511         outs() << getReversedLocWithContext(
 512             symbolize(IP, ShowCanonicalFnName, ShowPseudoProbe));
 513       }
 514       outs() << "\n";
 515     }
 516
 517     if (Disassembled) {
 518       const MCInstrDesc &MCDesc = MII->get(Inst.getOpcode());
 519
 520       // Record instruction size.
 521       AddressToInstSizeMap[Address] = Size;
 522
 523       // Populate address maps.
 524       CodeAddressVec.push_back(Address);
 525       if (MCDesc.isCall()) {
 526         CallAddressSet.insert(Address);
 527         UncondBranchAddrSet.insert(Address);
 528       } else if (MCDesc.isReturn()) {
 529         RetAddressSet.insert(Address);
 530         UncondBranchAddrSet.insert(Address);
 531       } else if (MCDesc.isBranch()) {
 532         if (MCDesc.isUnconditionalBranch())
 533           UncondBranchAddrSet.insert(Address);
 534         BranchAddressSet.insert(Address);
 535       }
 536
 537       // Record potential call targets for tail frame inference later-on.
 538       if (InferMissingFrames && FRange) {
 539         uint64_t Target = 0;
 540         MIA->evaluateBranch(Inst, Address, Size, Target);
 541         if (MCDesc.isCall()) {
 542           // Indirect call targets are unknown at this point. Recording the
 543           // unknown target (zero) for further LBR-based refinement.
 544           MissingContextInferrer->CallEdges[Address].insert(Target);
 545         } else if (MCDesc.isUnconditionalBranch()) {
 546           assert(Target &&
 547                  "target should be known for unconditional direct branch");
 548           // Any inter-function unconditional jump is considered tail call at
 549           // this point. This is not 100% accurate and could further be
 550           // optimized based on some source annotation.
 551           FuncRange *ToFRange = findFuncRange(Target);
 552           if (ToFRange && ToFRange->Func != FRange->Func)
 553             MissingContextInferrer->TailCallEdges[Address].insert(Target);
 554           LLVM_DEBUG({
 555             dbgs() << "Direct Tail call: " << format("%8" PRIx64 ":", Address);
 556             IPrinter->printInst(&Inst, Address + Size, "", *STI.get(), dbgs());
 557             dbgs() << "\n";
 558           });
 559         } else if (MCDesc.isIndirectBranch() && MCDesc.isBarrier()) {
 560           // This is an indirect branch but not necessarily an indirect tail
 561           // call. The isBarrier check is to filter out conditional branch.
 562           // Similar with indirect call targets, recording the unknown target
 563           // (zero) for further LBR-based refinement.
 564           MissingContextInferrer->TailCallEdges[Address].insert(Target);
 565           LLVM_DEBUG({
 566             dbgs() << "Indirect Tail call: "
 567                    << format("%8" PRIx64 ":", Address);
 568             IPrinter->printInst(&Inst, Address + Size, "", *STI.get(), dbgs());
 569             dbgs() << "\n";
 570           });
 571         }
 572       }
 573
 574       if (InvalidInstLength) {
 575         AddrsWithInvalidInstruction.insert(
 576             {Address - InvalidInstLength, Address - 1});
 577         InvalidInstLength = 0;
 578       }
 579     } else {
 580       InvalidInstLength += Size;
 581     }
 582
 583     Address += Size;
 584   }
 585
 586   if (InvalidInstLength)
 587     AddrsWithInvalidInstruction.insert(
 588         {Address - InvalidInstLength, Address - 1});
 589
 590   if (ShowDisassembly)
 591     outs() << "\n";
 592
 593   return true;
 594 }
 595
 596 void ProfiledBinary::setUpDisassembler(const ELFObjectFileBase *Obj) {
 597   const Target *TheTarget = getTarget(Obj);
 598   std::string TripleName = TheTriple.getTriple();
 599   StringRef FileName = Obj->getFileName();
 600
 601   MRI.reset(TheTarget->createMCRegInfo(TripleName));
 602   if (!MRI)
 603     exitWithError("no register info for target " + TripleName, FileName);
 604
 605   MCTargetOptions MCOptions;
 606   AsmInfo.reset(TheTarget->createMCAsmInfo(*MRI, TripleName, MCOptions));
 607   if (!AsmInfo)
 608     exitWithError("no assembly info for target " + TripleName, FileName);
 609
 610   Expected<SubtargetFeatures> Features = Obj->getFeatures();
 611   if (!Features)
 612     exitWithError(Features.takeError(), FileName);
 613   STI.reset(
 614       TheTarget->createMCSubtargetInfo(TripleName, "", Features->getString()));
 615   if (!STI)
 616     exitWithError("no subtarget info for target " + TripleName, FileName);
 617
 618   MII.reset(TheTarget->createMCInstrInfo());
 619   if (!MII)
 620     exitWithError("no instruction info for target " + TripleName, FileName);
 621
 622   MCContext Ctx(Triple(TripleName), AsmInfo.get(), MRI.get(), STI.get());
 623   std::unique_ptr<MCObjectFileInfo> MOFI(
 624       TheTarget->createMCObjectFileInfo(Ctx, /*PIC=*/false));
 625   Ctx.setObjectFileInfo(MOFI.get());
 626   DisAsm.reset(TheTarget->createMCDisassembler(*STI, Ctx));
 627   if (!DisAsm)
 628     exitWithError("no disassembler for target " + TripleName, FileName);
 629
 630   MIA.reset(TheTarget->createMCInstrAnalysis(MII.get()));
 631
 632   int AsmPrinterVariant = AsmInfo->getAssemblerDialect();
 633   IPrinter.reset(TheTarget->createMCInstPrinter(
 634       Triple(TripleName), AsmPrinterVariant, *AsmInfo, *MII, *MRI));
 635   IPrinter->setPrintBranchImmAsAddress(true);
 636 }
 637
 638 void ProfiledBinary::disassemble(const ELFObjectFileBase *Obj) {
 639   // Set up disassembler and related components.
 640   setUpDisassembler(Obj);
 641
 642   // Create a mapping from virtual address to symbol name. The symbols in text
 643   // sections are the candidates to dissassemble.
 644   std::map<SectionRef, SectionSymbolsTy> AllSymbols;
 645   StringRef FileName = Obj->getFileName();
 646   for (const SymbolRef &Symbol : Obj->symbols()) {
 647     const uint64_t Addr = unwrapOrError(Symbol.getAddress(), FileName);
 648     const StringRef Name = unwrapOrError(Symbol.getName(), FileName);
 649     section_iterator SecI = unwrapOrError(Symbol.getSection(), FileName);
 650     if (SecI != Obj->section_end())
 651       AllSymbols[*SecI].push_back(SymbolInfoTy(Addr, Name, ELF::STT_NOTYPE));
 652   }
 653
 654   // Sort all the symbols. Use a stable sort to stabilize the output.
 655   for (std::pair<const SectionRef, SectionSymbolsTy> &SecSyms : AllSymbols)
 656     stable_sort(SecSyms.second);
 657
 658   assert((DisassembleFunctionSet.empty() || ShowDisassemblyOnly) &&
 659          "Functions to disassemble should be only specified together with "
 660          "--show-disassembly-only");
 661
 662   if (ShowDisassemblyOnly)
 663     outs() << "\nDisassembly of " << FileName << ":\n";
 664
 665   // Dissassemble a text section.
 666   for (section_iterator SI = Obj->section_begin(), SE = Obj->section_end();
 667        SI != SE; ++SI) {
 668     const SectionRef &Section = *SI;
 669     if (!Section.isText())
 670       continue;
 671
 672     uint64_t ImageLoadAddr = getPreferredBaseAddress();
 673     uint64_t SectionAddress = Section.getAddress() - ImageLoadAddr;
 674     uint64_t SectSize = Section.getSize();
 675     if (!SectSize)
 676       continue;
 677
 678     // Register the text section.
 679     TextSections.insert({SectionAddress, SectSize});
 680
 681     StringRef SectionName = unwrapOrError(Section.getName(), FileName);
 682
 683     if (ShowDisassemblyOnly) {
 684       outs() << "\nDisassembly of section " << SectionName;
 685       outs() << " [" << format("0x%" PRIx64, Section.getAddress()) << ", "
 686              << format("0x%" PRIx64, Section.getAddress() + SectSize)
 687              << "]:\n\n";
 688     }
 689
 690     if (SectionName == ".plt")
 691       continue;
 692
 693     // Get the section data.
 694     ArrayRef<uint8_t> Bytes =
 695         arrayRefFromStringRef(unwrapOrError(Section.getContents(), FileName));
 696
 697     // Get the list of all the symbols in this section.
 698     SectionSymbolsTy &Symbols = AllSymbols[Section];
 699
 700     // Disassemble symbol by symbol.
 701     for (std::size_t SI = 0, SE = Symbols.size(); SI != SE; ++SI) {
 702       if (!dissassembleSymbol(SI, Bytes, Symbols, Section))
 703         exitWithError("disassembling error", FileName);
 704     }
 705   }
 706
 707   if (!AddrsWithInvalidInstruction.empty()) {
 708     if (ShowDetailedWarning) {
 709       for (auto &Addr : AddrsWithInvalidInstruction) {
 710         WithColor::warning()
 711             << "Invalid instructions at " << format("%8" PRIx64, Addr.first)
 712             << " - " << format("%8" PRIx64, Addr.second) << "\n";
 713       }
 714     }
 715     WithColor::warning() << "Found " << AddrsWithInvalidInstruction.size()
 716                          << " invalid instructions\n";
 717     AddrsWithInvalidInstruction.clear();
 718   }
 719
 720   // Dissassemble rodata section to check if FS discriminator symbol exists.
 721   checkUseFSDiscriminator(Obj, AllSymbols);
 722 }
 723
 724 void ProfiledBinary::checkUseFSDiscriminator(
 725     const ELFObjectFileBase *Obj,
 726     std::map<SectionRef, SectionSymbolsTy> &AllSymbols) {
 727   const char *FSDiscriminatorVar = "__llvm_fs_discriminator__";
 728   for (section_iterator SI = Obj->section_begin(), SE = Obj->section_end();
 729        SI != SE; ++SI) {
 730     const SectionRef &Section = *SI;
 731     if (!Section.isData() || Section.getSize() == 0)
 732       continue;
 733     SectionSymbolsTy &Symbols = AllSymbols[Section];
 734
 735     for (std::size_t SI = 0, SE = Symbols.size(); SI != SE; ++SI) {
 736       if (Symbols[SI].Name == FSDiscriminatorVar) {
 737         UseFSDiscriminator = true;
 738         return;
 739       }
 740     }
 741   }
 742 }
 743
 744 void ProfiledBinary::populateElfSymbolAddressList(
 745     const ELFObjectFileBase *Obj) {
 746   // Create a mapping from virtual address to symbol GUID and the other way
 747   // around.
 748   StringRef FileName = Obj->getFileName();
 749   for (const SymbolRef &Symbol : Obj->symbols()) {
 750     const uint64_t Addr = unwrapOrError(Symbol.getAddress(), FileName);
 751     const StringRef Name = unwrapOrError(Symbol.getName(), FileName);
 752     uint64_t GUID = Function::getGUID(Name);
 753     SymbolStartAddrs[GUID] = Addr;
 754     StartAddrToSymMap.emplace(Addr, GUID);
 755   }
 756 }
 757
 758 void ProfiledBinary::loadSymbolsFromDWARFUnit(DWARFUnit &CompilationUnit) {
 759   for (const auto &DieInfo : CompilationUnit.dies()) {
 760     llvm::DWARFDie Die(&CompilationUnit, &DieInfo);
 761
 762     if (!Die.isSubprogramDIE())
 763       continue;
 764     auto Name = Die.getName(llvm::DINameKind::LinkageName);
 765     if (!Name)
 766       Name = Die.getName(llvm::DINameKind::ShortName);
 767     if (!Name)
 768       continue;
 769
 770     auto RangesOrError = Die.getAddressRanges();
 771     if (!RangesOrError)
 772       continue;
 773     const DWARFAddressRangesVector &Ranges = RangesOrError.get();
 774
 775     if (Ranges.empty())
 776       continue;
 777
 778     // Different DWARF symbols can have same function name, search or create
 779     // BinaryFunction indexed by the name.
 780     auto Ret = BinaryFunctions.emplace(Name, BinaryFunction());
 781     auto &Func = Ret.first->second;
 782     if (Ret.second)
 783       Func.FuncName = Ret.first->first;
 784
 785     for (const auto &Range : Ranges) {
 786       uint64_t StartAddress = Range.LowPC;
 787       uint64_t EndAddress = Range.HighPC;
 788
 789       if (EndAddress <= StartAddress ||
 790           StartAddress < getPreferredBaseAddress())
 791         continue;
 792
 793       // We may want to know all ranges for one function. Here group the
 794       // ranges and store them into BinaryFunction.
 795       Func.Ranges.emplace_back(StartAddress, EndAddress);
 796
 797       auto R = StartAddrToFuncRangeMap.emplace(StartAddress, FuncRange());
 798       if (R.second) {
 799         FuncRange &FRange = R.first->second;
 800         FRange.Func = &Func;
 801         FRange.StartAddress = StartAddress;
 802         FRange.EndAddress = EndAddress;
 803       } else {
 804         AddrsWithMultipleSymbols.insert(StartAddress);
 805         if (ShowDetailedWarning)
 806           WithColor::warning()
 807               << "Duplicated symbol start address at "
 808               << format("%8" PRIx64, StartAddress) << " "
 809               << R.first->second.getFuncName() << " and " << Name << "\n";
 810       }
 811     }
 812   }
 813 }
 814
 815 void ProfiledBinary::loadSymbolsFromDWARF(ObjectFile &Obj) {
 816   auto DebugContext = llvm::DWARFContext::create(
 817       Obj, DWARFContext::ProcessDebugRelocations::Process, nullptr, DWPPath);
 818   if (!DebugContext)
 819     exitWithError("Error creating the debug info context", Path);
 820
 821   for (const auto &CompilationUnit : DebugContext->compile_units())
 822     loadSymbolsFromDWARFUnit(*CompilationUnit.get());
 823
 824   // Handles DWO sections that can either be in .o, .dwo or .dwp files.
 825   uint32_t NumOfDWOMissing = 0;
 826   for (const auto &CompilationUnit : DebugContext->compile_units()) {
 827     DWARFUnit *const DwarfUnit = CompilationUnit.get();
 828     if (DwarfUnit->getDWOId()) {
 829       DWARFUnit *DWOCU = DwarfUnit->getNonSkeletonUnitDIE(false).getDwarfUnit();
 830       if (!DWOCU->isDWOUnit()) {
 831         NumOfDWOMissing++;
 832         if (ShowDetailedWarning) {
 833           std::string DWOName = dwarf::toString(
 834               DwarfUnit->getUnitDIE().find(
 835                   {dwarf::DW_AT_dwo_name, dwarf::DW_AT_GNU_dwo_name}),
 836               "");
 837           WithColor::warning() << "DWO debug information for " << DWOName
 838                                << " was not loaded.\n";
 839         }
 840         continue;
 841       }
 842       loadSymbolsFromDWARFUnit(*DWOCU);
 843     }
 844   }
 845
 846   if (NumOfDWOMissing)
 847     WithColor::warning()
 848         << " DWO debug information was not loaded for " << NumOfDWOMissing
 849         << " modules. Please check the .o, .dwo or .dwp path.\n";
 850   if (BinaryFunctions.empty())
 851     WithColor::warning() << "Loading of DWARF info completed, but no binary "
 852                             "functions have been retrieved.\n";
 853   // Populate the hash binary function map for MD5 function name lookup. This
 854   // is done after BinaryFunctions are finalized.
 855   for (auto &BinaryFunction : BinaryFunctions) {
 856     HashBinaryFunctions[MD5Hash(StringRef(BinaryFunction.first))] =
 857         &BinaryFunction.second;
 858   }
 859
 860   if (!AddrsWithMultipleSymbols.empty()) {
 861     WithColor::warning() << "Found " << AddrsWithMultipleSymbols.size()
 862                          << " start addresses with multiple symbols\n";
 863     AddrsWithMultipleSymbols.clear();
 864   }
 865 }
 866
 867 void ProfiledBinary::populateSymbolListFromDWARF(
 868     ProfileSymbolList &SymbolList) {
 869   for (auto &I : StartAddrToFuncRangeMap)
 870     SymbolList.add(I.second.getFuncName());
 871 }
 872
 873 symbolize::LLVMSymbolizer::Options ProfiledBinary::getSymbolizerOpts() const {
 874   symbolize::LLVMSymbolizer::Options SymbolizerOpts;
 875   SymbolizerOpts.PrintFunctions =
 876       DILineInfoSpecifier::FunctionNameKind::LinkageName;
 877   SymbolizerOpts.Demangle = false;
 878   SymbolizerOpts.DefaultArch = TheTriple.getArchName().str();
 879   SymbolizerOpts.UseSymbolTable = false;
 880   SymbolizerOpts.RelativeAddresses = false;
 881   SymbolizerOpts.DWPName = DWPPath;
 882   return SymbolizerOpts;
 883 }
 884
 885 SampleContextFrameVector ProfiledBinary::symbolize(const InstructionPointer &IP,
 886                                                    bool UseCanonicalFnName,
 887                                                    bool UseProbeDiscriminator) {
 888   assert(this == IP.Binary &&
 889          "Binary should only symbolize its own instruction");
 890   auto Addr = object::SectionedAddress{IP.Address,
 891                                        object::SectionedAddress::UndefSection};
 892   DIInliningInfo InlineStack = unwrapOrError(
 893       Symbolizer->symbolizeInlinedCode(SymbolizerPath.str(), Addr),
 894       SymbolizerPath);
 895
 896   SampleContextFrameVector CallStack;
 897   for (int32_t I = InlineStack.getNumberOfFrames() - 1; I >= 0; I--) {
 898     const auto &CallerFrame = InlineStack.getFrame(I);
 899     if (CallerFrame.FunctionName.empty() ||
 900         (CallerFrame.FunctionName == "<invalid>"))
 901       break;
 902
 903     StringRef FunctionName(CallerFrame.FunctionName);
 904     if (UseCanonicalFnName)
 905       FunctionName = FunctionSamples::getCanonicalFnName(FunctionName);
 906
 907     uint32_t Discriminator = CallerFrame.Discriminator;
 908     uint32_t LineOffset = (CallerFrame.Line - CallerFrame.StartLine) & 0xffff;
 909     if (UseProbeDiscriminator) {
 910       LineOffset =
 911           PseudoProbeDwarfDiscriminator::extractProbeIndex(Discriminator);
 912       Discriminator = 0;
 913     }
 914
 915     LineLocation Line(LineOffset, Discriminator);
 916     auto It = NameStrings.insert(FunctionName.str());
 917     CallStack.emplace_back(FunctionId(StringRef(*It.first)), Line);
 918   }
 919
 920   return CallStack;
 921 }
 922
 923 void ProfiledBinary::computeInlinedContextSizeForRange(uint64_t RangeBegin,
 924                                                        uint64_t RangeEnd) {
 925   InstructionPointer IP(this, RangeBegin, true);
 926
 927   if (IP.Address != RangeBegin)
 928     WithColor::warning() << "Invalid start instruction at "
 929                          << format("%8" PRIx64, RangeBegin) << "\n";
 930
 931   if (IP.Address >= RangeEnd)
 932     return;
 933
 934   do {
 935     const SampleContextFrameVector SymbolizedCallStack =
 936         getFrameLocationStack(IP.Address, UsePseudoProbes);
 937     uint64_t Size = AddressToInstSizeMap[IP.Address];
 938     // Record instruction size for the corresponding context
 939     FuncSizeTracker.addInstructionForContext(SymbolizedCallStack, Size);
 940
 941   } while (IP.advance() && IP.Address < RangeEnd);
 942 }
 943
 944 void ProfiledBinary::computeInlinedContextSizeForFunc(
 945     const BinaryFunction *Func) {
 946   // Note that a function can be spilt into multiple ranges, so compute for all
 947   // ranges of the function.
 948   for (const auto &Range : Func->Ranges)
 949     computeInlinedContextSizeForRange(Range.first, Range.second);
 950
 951   // Track optimized-away inlinee for probed binary. A function inlined and then
 952   // optimized away should still have their probes left over in places.
 953   if (usePseudoProbes()) {
 954     auto I = TopLevelProbeFrameMap.find(Func->FuncName);
 955     if (I != TopLevelProbeFrameMap.end()) {
 956       BinarySizeContextTracker::ProbeFrameStack ProbeContext;
 957       FuncSizeTracker.trackInlineesOptimizedAway(ProbeDecoder, *I->second,
 958                                                  ProbeContext);
 959     }
 960   }
 961 }
 962
 963 void ProfiledBinary::inferMissingFrames(
 964     const SmallVectorImpl<uint64_t> &Context,
 965     SmallVectorImpl<uint64_t> &NewContext) {
 966   MissingContextInferrer->inferMissingFrames(Context, NewContext);
 967 }
 968
 969 InstructionPointer::InstructionPointer(const ProfiledBinary *Binary,
 970                                        uint64_t Address, bool RoundToNext)
 971     : Binary(Binary), Address(Address) {
 972   Index = Binary->getIndexForAddr(Address);
 973   if (RoundToNext) {
 974     // we might get address which is not the code
 975     // it should round to the next valid address
 976     if (Index >= Binary->getCodeAddrVecSize())
 977       this->Address = UINT64_MAX;
 978     else
 979       this->Address = Binary->getAddressforIndex(Index);
 980   }
 981 }
 982
 983 bool InstructionPointer::advance() {
 984   Index++;
 985   if (Index >= Binary->getCodeAddrVecSize()) {
 986     Address = UINT64_MAX;
 987     return false;
 988   }
 989   Address = Binary->getAddressforIndex(Index);
 990   return true;
 991 }
 992
 993 bool InstructionPointer::backward() {
 994   if (Index == 0) {
 995     Address = 0;
 996     return false;
 997   }
 998   Index--;
 999   Address = Binary->getAddressforIndex(Index);
1000   return true;
1001 }
1002
1003 void InstructionPointer::update(uint64_t Addr) {
1004   Address = Addr;
1005   Index = Binary->getIndexForAddr(Address);
1006 }
1007
1008 } // end namespace sampleprof
1009 } // end namespace llvm