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 "ProfileGenerator.h"
12 #include "llvm/ADT/Triple.h"
13 #include "llvm/Demangle/Demangle.h"
14 #include "llvm/IR/DebugInfoMetadata.h"
15 #include "llvm/MC/TargetRegistry.h"
16 #include "llvm/Support/CommandLine.h"
17 #include "llvm/Support/Format.h"
18 #include "llvm/Support/TargetSelect.h"
19 
20 #define DEBUG_TYPE "load-binary"
21 
22 using namespace llvm;
23 using namespace sampleprof;
24 
25 cl::opt<bool> ShowDisassemblyOnly("show-disassembly-only", cl::init(false),
26                                   cl::ZeroOrMore,
27                                   cl::desc("Print disassembled code."));
28 
29 cl::opt<bool> ShowSourceLocations("show-source-locations", cl::init(false),
30                                   cl::ZeroOrMore,
31                                   cl::desc("Print source locations."));
32 
33 static cl::opt<bool>
34     ShowCanonicalFnName("show-canonical-fname", cl::init(false), cl::ZeroOrMore,
35                         cl::desc("Print canonical function name."));
36 
37 static cl::opt<bool> ShowPseudoProbe(
38     "show-pseudo-probe", cl::init(false), cl::ZeroOrMore,
39     cl::desc("Print pseudo probe section and disassembled info."));
40 
41 static cl::opt<bool> UseDwarfCorrelation(
42     "use-dwarf-correlation", cl::init(false), cl::ZeroOrMore,
43     cl::desc("Use dwarf for profile correlation even when binary contains "
44              "pseudo probe."));
45 
46 static cl::list<std::string> DisassembleFunctions(
47     "disassemble-functions", cl::CommaSeparated,
48     cl::desc("List of functions to print disassembly for. Accept demangled "
49              "names only. Only work with show-disassembly-only"));
50 
51 namespace llvm {
52 namespace sampleprof {
53 
54 static const Target *getTarget(const ObjectFile *Obj) {
55   Triple TheTriple = Obj->makeTriple();
56   std::string Error;
57   std::string ArchName;
58   const Target *TheTarget =
59       TargetRegistry::lookupTarget(ArchName, TheTriple, Error);
60   if (!TheTarget)
61     exitWithError(Error, Obj->getFileName());
62   return TheTarget;
63 }
64 
65 void BinarySizeContextTracker::addInstructionForContext(
66     const SampleContextFrameVector &Context, uint32_t InstrSize) {
67   ContextTrieNode *CurNode = &RootContext;
68   bool IsLeaf = true;
69   for (const auto &Callsite : reverse(Context)) {
70     StringRef CallerName = Callsite.FuncName;
71     LineLocation CallsiteLoc = IsLeaf ? LineLocation(0, 0) : Callsite.Location;
72     CurNode = CurNode->getOrCreateChildContext(CallsiteLoc, CallerName);
73     IsLeaf = false;
74   }
75 
76   CurNode->addFunctionSize(InstrSize);
77 }
78 
79 uint32_t
80 BinarySizeContextTracker::getFuncSizeForContext(const SampleContext &Context) {
81   ContextTrieNode *CurrNode = &RootContext;
82   ContextTrieNode *PrevNode = nullptr;
83   SampleContextFrames Frames = Context.getContextFrames();
84   int32_t I = Frames.size() - 1;
85   Optional<uint32_t> Size;
86 
87   // Start from top-level context-less function, traverse down the reverse
88   // context trie to find the best/longest match for given context, then
89   // retrieve the size.
90 
91   while (CurrNode && I >= 0) {
92     // Process from leaf function to callers (added to context).
93     const auto &ChildFrame = Frames[I--];
94     PrevNode = CurrNode;
95     CurrNode =
96         CurrNode->getChildContext(ChildFrame.Location, ChildFrame.FuncName);
97     if (CurrNode && CurrNode->getFunctionSize().hasValue())
98       Size = CurrNode->getFunctionSize().getValue();
99   }
100 
101   // If we traversed all nodes along the path of the context and haven't
102   // found a size yet, pivot to look for size from sibling nodes, i.e size
103   // of inlinee under different context.
104   if (!Size.hasValue()) {
105     if (!CurrNode)
106       CurrNode = PrevNode;
107     while (!Size.hasValue() && CurrNode &&
108            !CurrNode->getAllChildContext().empty()) {
109       CurrNode = &CurrNode->getAllChildContext().begin()->second;
110       if (CurrNode->getFunctionSize().hasValue())
111         Size = CurrNode->getFunctionSize().getValue();
112     }
113   }
114 
115   assert(Size.hasValue() && "We should at least find one context size.");
116   return Size.getValue();
117 }
118 
119 void BinarySizeContextTracker::trackInlineesOptimizedAway(
120     MCPseudoProbeDecoder &ProbeDecoder) {
121   ProbeFrameStack ProbeContext;
122   for (const auto &Child : ProbeDecoder.getDummyInlineRoot().getChildren())
123     trackInlineesOptimizedAway(ProbeDecoder, *Child.second.get(), ProbeContext);
124 }
125 
126 void BinarySizeContextTracker::trackInlineesOptimizedAway(
127     MCPseudoProbeDecoder &ProbeDecoder,
128     MCDecodedPseudoProbeInlineTree &ProbeNode, ProbeFrameStack &ProbeContext) {
129   StringRef FuncName =
130       ProbeDecoder.getFuncDescForGUID(ProbeNode.Guid)->FuncName;
131   ProbeContext.emplace_back(FuncName, 0);
132 
133   // This ProbeContext has a probe, so it has code before inlining and
134   // optimization. Make sure we mark its size as known.
135   if (!ProbeNode.getProbes().empty()) {
136     ContextTrieNode *SizeContext = &RootContext;
137     for (auto &ProbeFrame : reverse(ProbeContext)) {
138       StringRef CallerName = ProbeFrame.first;
139       LineLocation CallsiteLoc(ProbeFrame.second, 0);
140       SizeContext =
141           SizeContext->getOrCreateChildContext(CallsiteLoc, CallerName);
142     }
143     // Add 0 size to make known.
144     SizeContext->addFunctionSize(0);
145   }
146 
147   // DFS down the probe inline tree
148   for (const auto &ChildNode : ProbeNode.getChildren()) {
149     InlineSite Location = ChildNode.first;
150     ProbeContext.back().second = std::get<1>(Location);
151     trackInlineesOptimizedAway(ProbeDecoder, *ChildNode.second.get(), ProbeContext);
152   }
153 
154   ProbeContext.pop_back();
155 }
156 
157 void ProfiledBinary::load() {
158   // Attempt to open the binary.
159   OwningBinary<Binary> OBinary = unwrapOrError(createBinary(Path), Path);
160   Binary &Binary = *OBinary.getBinary();
161 
162   auto *Obj = dyn_cast<ELFObjectFileBase>(&Binary);
163   if (!Obj)
164     exitWithError("not a valid Elf image", Path);
165 
166   TheTriple = Obj->makeTriple();
167   // Current only support X86
168   if (!TheTriple.isX86())
169     exitWithError("unsupported target", TheTriple.getTriple());
170   LLVM_DEBUG(dbgs() << "Loading " << Path << "\n");
171 
172   // Find the preferred load address for text sections.
173   setPreferredTextSegmentAddresses(Obj);
174 
175   // Decode pseudo probe related section
176   decodePseudoProbe(Obj);
177 
178   // Load debug info of subprograms from DWARF section.
179   loadSymbolsFromDWARF(*dyn_cast<ObjectFile>(&Binary));
180 
181   // Disassemble the text sections.
182   disassemble(Obj);
183 
184   // Track size for optimized inlinees when probe is available
185   if (UsePseudoProbes && TrackFuncContextSize)
186     FuncSizeTracker.trackInlineesOptimizedAway(ProbeDecoder);
187 
188   // Use function start and return address to infer prolog and epilog
189   ProEpilogTracker.inferPrologOffsets(StartOffset2FuncRangeMap);
190   ProEpilogTracker.inferEpilogOffsets(RetOffsets);
191 
192   // TODO: decode other sections.
193 }
194 
195 bool ProfiledBinary::inlineContextEqual(uint64_t Address1, uint64_t Address2) {
196   uint64_t Offset1 = virtualAddrToOffset(Address1);
197   uint64_t Offset2 = virtualAddrToOffset(Address2);
198   const SampleContextFrameVector &Context1 = getFrameLocationStack(Offset1);
199   const SampleContextFrameVector &Context2 = getFrameLocationStack(Offset2);
200   if (Context1.size() != Context2.size())
201     return false;
202   if (Context1.empty())
203     return false;
204   // The leaf frame contains location within the leaf, and it
205   // needs to be remove that as it's not part of the calling context
206   return std::equal(Context1.begin(), Context1.begin() + Context1.size() - 1,
207                     Context2.begin(), Context2.begin() + Context2.size() - 1);
208 }
209 
210 SampleContextFrameVector
211 ProfiledBinary::getExpandedContext(const SmallVectorImpl<uint64_t> &Stack,
212                                    bool &WasLeafInlined) {
213   SampleContextFrameVector ContextVec;
214   // Process from frame root to leaf
215   for (auto Address : Stack) {
216     uint64_t Offset = virtualAddrToOffset(Address);
217     const SampleContextFrameVector &ExpandedContext =
218         getFrameLocationStack(Offset);
219     // An instruction without a valid debug line will be ignored by sample
220     // processing
221     if (ExpandedContext.empty())
222       return SampleContextFrameVector();
223     // Set WasLeafInlined to the size of inlined frame count for the last
224     // address which is leaf
225     WasLeafInlined = (ExpandedContext.size() > 1);
226     ContextVec.append(ExpandedContext);
227   }
228 
229   // Replace with decoded base discriminator
230   for (auto &Frame : ContextVec) {
231     Frame.Location.Discriminator = ProfileGeneratorBase::getBaseDiscriminator(
232         Frame.Location.Discriminator);
233   }
234 
235   assert(ContextVec.size() && "Context length should be at least 1");
236 
237   // Compress the context string except for the leaf frame
238   auto LeafFrame = ContextVec.back();
239   LeafFrame.Location = LineLocation(0, 0);
240   ContextVec.pop_back();
241   CSProfileGenerator::compressRecursionContext(ContextVec);
242   CSProfileGenerator::trimContext(ContextVec);
243   ContextVec.push_back(LeafFrame);
244   return ContextVec;
245 }
246 
247 template <class ELFT>
248 void ProfiledBinary::setPreferredTextSegmentAddresses(const ELFFile<ELFT> &Obj, StringRef FileName) {
249   const auto &PhdrRange = unwrapOrError(Obj.program_headers(), FileName);
250   // FIXME: This should be the page size of the system running profiling.
251   // However such info isn't available at post-processing time, assuming
252   // 4K page now. Note that we don't use EXEC_PAGESIZE from <linux/param.h>
253   // because we may build the tools on non-linux.
254   uint32_t PageSize = 0x1000;
255   for (const typename ELFT::Phdr &Phdr : PhdrRange) {
256     if ((Phdr.p_type == ELF::PT_LOAD) && (Phdr.p_flags & ELF::PF_X)) {
257         // Segments will always be loaded at a page boundary.
258         PreferredTextSegmentAddresses.push_back(Phdr.p_vaddr &
259                                                 ~(PageSize - 1U));
260         TextSegmentOffsets.push_back(Phdr.p_offset & ~(PageSize - 1U));
261       }
262   }
263 
264   if (PreferredTextSegmentAddresses.empty())
265     exitWithError("no executable segment found", FileName);
266 }
267 
268 void ProfiledBinary::setPreferredTextSegmentAddresses(const ELFObjectFileBase *Obj) {
269   if (const auto *ELFObj = dyn_cast<ELF32LEObjectFile>(Obj))
270     setPreferredTextSegmentAddresses(ELFObj->getELFFile(), Obj->getFileName());
271   else if (const auto *ELFObj = dyn_cast<ELF32BEObjectFile>(Obj))
272     setPreferredTextSegmentAddresses(ELFObj->getELFFile(), Obj->getFileName());
273   else if (const auto *ELFObj = dyn_cast<ELF64LEObjectFile>(Obj))
274     setPreferredTextSegmentAddresses(ELFObj->getELFFile(), Obj->getFileName());
275   else if (const auto *ELFObj = cast<ELF64BEObjectFile>(Obj))
276     setPreferredTextSegmentAddresses(ELFObj->getELFFile(), Obj->getFileName());
277   else
278     llvm_unreachable("invalid ELF object format");
279 }
280 
281 void ProfiledBinary::decodePseudoProbe(const ELFObjectFileBase *Obj) {
282   if (UseDwarfCorrelation)
283     return;
284 
285   StringRef FileName = Obj->getFileName();
286   for (section_iterator SI = Obj->section_begin(), SE = Obj->section_end();
287        SI != SE; ++SI) {
288     const SectionRef &Section = *SI;
289     StringRef SectionName = unwrapOrError(Section.getName(), FileName);
290 
291     if (SectionName == ".pseudo_probe_desc") {
292       StringRef Contents = unwrapOrError(Section.getContents(), FileName);
293       if (!ProbeDecoder.buildGUID2FuncDescMap(
294               reinterpret_cast<const uint8_t *>(Contents.data()),
295               Contents.size()))
296         exitWithError("Pseudo Probe decoder fail in .pseudo_probe_desc section");
297     } else if (SectionName == ".pseudo_probe") {
298       StringRef Contents = unwrapOrError(Section.getContents(), FileName);
299       if (!ProbeDecoder.buildAddress2ProbeMap(
300               reinterpret_cast<const uint8_t *>(Contents.data()),
301               Contents.size()))
302         exitWithError("Pseudo Probe decoder fail in .pseudo_probe section");
303       // set UsePseudoProbes flag, used for PerfReader
304       UsePseudoProbes = true;
305     }
306   }
307 
308   if (ShowPseudoProbe)
309     ProbeDecoder.printGUID2FuncDescMap(outs());
310 }
311 
312 void ProfiledBinary::setIsFuncEntry(uint64_t Offset, StringRef RangeSymName) {
313   // Note that the start offset of each ELF section can be a non-function
314   // symbol, we need to binary search for the start of a real function range.
315   auto *FuncRange = findFuncRangeForOffset(Offset);
316   // Skip external function symbol.
317   if (!FuncRange)
318     return;
319 
320   // Set IsFuncEntry to ture if the RangeSymName from ELF is equal to its
321   // DWARF-based function name.
322   if (!FuncRange->IsFuncEntry && FuncRange->getFuncName() == RangeSymName)
323     FuncRange->IsFuncEntry = true;
324 }
325 
326 bool ProfiledBinary::dissassembleSymbol(std::size_t SI, ArrayRef<uint8_t> Bytes,
327                                         SectionSymbolsTy &Symbols,
328                                         const SectionRef &Section) {
329   std::size_t SE = Symbols.size();
330   uint64_t SectionOffset = Section.getAddress() - getPreferredBaseAddress();
331   uint64_t SectSize = Section.getSize();
332   uint64_t StartOffset = Symbols[SI].Addr - getPreferredBaseAddress();
333   uint64_t NextStartOffset =
334       (SI + 1 < SE) ? Symbols[SI + 1].Addr - getPreferredBaseAddress()
335                     : SectionOffset + SectSize;
336   if (StartOffset > NextStartOffset)
337     return true;
338 
339   StringRef SymbolName =
340       ShowCanonicalFnName
341           ? FunctionSamples::getCanonicalFnName(Symbols[SI].Name)
342           : Symbols[SI].Name;
343   bool ShowDisassembly =
344       ShowDisassemblyOnly && (DisassembleFunctionSet.empty() ||
345                               DisassembleFunctionSet.count(SymbolName));
346   if (ShowDisassembly)
347     outs() << '<' << SymbolName << ">:\n";
348 
349   auto WarnInvalidInsts = [](uint64_t Start, uint64_t End) {
350     WithColor::warning() << "Invalid instructions at "
351                          << format("%8" PRIx64, Start) << " - "
352                          << format("%8" PRIx64, End) << "\n";
353   };
354 
355   uint64_t Offset = StartOffset;
356   // Size of a consecutive invalid instruction range starting from Offset -1
357   // backwards.
358   uint64_t InvalidInstLength = 0;
359   while (Offset < NextStartOffset) {
360     MCInst Inst;
361     uint64_t Size;
362     // Disassemble an instruction.
363     bool Disassembled =
364         DisAsm->getInstruction(Inst, Size, Bytes.slice(Offset - SectionOffset),
365                                Offset + getPreferredBaseAddress(), nulls());
366     if (Size == 0)
367       Size = 1;
368 
369     if (ShowDisassembly) {
370       if (ShowPseudoProbe) {
371         ProbeDecoder.printProbeForAddress(outs(),
372                                           Offset + getPreferredBaseAddress());
373       }
374       outs() << format("%8" PRIx64 ":", Offset + getPreferredBaseAddress());
375       size_t Start = outs().tell();
376       if (Disassembled)
377         IPrinter->printInst(&Inst, Offset + Size, "", *STI.get(), outs());
378       else
379         outs() << "\t<unknown>";
380       if (ShowSourceLocations) {
381         unsigned Cur = outs().tell() - Start;
382         if (Cur < 40)
383           outs().indent(40 - Cur);
384         InstructionPointer IP(this, Offset);
385         outs() << getReversedLocWithContext(
386             symbolize(IP, ShowCanonicalFnName, ShowPseudoProbe));
387       }
388       outs() << "\n";
389     }
390 
391     if (Disassembled) {
392       const MCInstrDesc &MCDesc = MII->get(Inst.getOpcode());
393 
394       // Record instruction size.
395       Offset2InstSizeMap[Offset] = Size;
396 
397       // Populate address maps.
398       CodeAddrOffsets.push_back(Offset);
399       if (MCDesc.isCall())
400         CallOffsets.insert(Offset);
401       else if (MCDesc.isReturn())
402         RetOffsets.insert(Offset);
403       else if (MCDesc.isBranch())
404         BranchOffsets.insert(Offset);
405 
406       if (InvalidInstLength) {
407         WarnInvalidInsts(Offset - InvalidInstLength, Offset - 1);
408         InvalidInstLength = 0;
409       }
410     } else {
411       InvalidInstLength += Size;
412     }
413 
414     Offset += Size;
415   }
416 
417   if (InvalidInstLength)
418     WarnInvalidInsts(Offset - InvalidInstLength, Offset - 1);
419 
420   if (ShowDisassembly)
421     outs() << "\n";
422 
423   setIsFuncEntry(StartOffset, Symbols[SI].Name);
424 
425   return true;
426 }
427 
428 void ProfiledBinary::setUpDisassembler(const ELFObjectFileBase *Obj) {
429   const Target *TheTarget = getTarget(Obj);
430   std::string TripleName = TheTriple.getTriple();
431   StringRef FileName = Obj->getFileName();
432 
433   MRI.reset(TheTarget->createMCRegInfo(TripleName));
434   if (!MRI)
435     exitWithError("no register info for target " + TripleName, FileName);
436 
437   MCTargetOptions MCOptions;
438   AsmInfo.reset(TheTarget->createMCAsmInfo(*MRI, TripleName, MCOptions));
439   if (!AsmInfo)
440     exitWithError("no assembly info for target " + TripleName, FileName);
441 
442   SubtargetFeatures Features = Obj->getFeatures();
443   STI.reset(
444       TheTarget->createMCSubtargetInfo(TripleName, "", Features.getString()));
445   if (!STI)
446     exitWithError("no subtarget info for target " + TripleName, FileName);
447 
448   MII.reset(TheTarget->createMCInstrInfo());
449   if (!MII)
450     exitWithError("no instruction info for target " + TripleName, FileName);
451 
452   MCContext Ctx(Triple(TripleName), AsmInfo.get(), MRI.get(), STI.get());
453   std::unique_ptr<MCObjectFileInfo> MOFI(
454       TheTarget->createMCObjectFileInfo(Ctx, /*PIC=*/false));
455   Ctx.setObjectFileInfo(MOFI.get());
456   DisAsm.reset(TheTarget->createMCDisassembler(*STI, Ctx));
457   if (!DisAsm)
458     exitWithError("no disassembler for target " + TripleName, FileName);
459 
460   MIA.reset(TheTarget->createMCInstrAnalysis(MII.get()));
461 
462   int AsmPrinterVariant = AsmInfo->getAssemblerDialect();
463   IPrinter.reset(TheTarget->createMCInstPrinter(
464       Triple(TripleName), AsmPrinterVariant, *AsmInfo, *MII, *MRI));
465   IPrinter->setPrintBranchImmAsAddress(true);
466 }
467 
468 void ProfiledBinary::disassemble(const ELFObjectFileBase *Obj) {
469   // Set up disassembler and related components.
470   setUpDisassembler(Obj);
471 
472   // Create a mapping from virtual address to symbol name. The symbols in text
473   // sections are the candidates to dissassemble.
474   std::map<SectionRef, SectionSymbolsTy> AllSymbols;
475   StringRef FileName = Obj->getFileName();
476   for (const SymbolRef &Symbol : Obj->symbols()) {
477     const uint64_t Addr = unwrapOrError(Symbol.getAddress(), FileName);
478     const StringRef Name = unwrapOrError(Symbol.getName(), FileName);
479     section_iterator SecI = unwrapOrError(Symbol.getSection(), FileName);
480     if (SecI != Obj->section_end())
481       AllSymbols[*SecI].push_back(SymbolInfoTy(Addr, Name, ELF::STT_NOTYPE));
482   }
483 
484   // Sort all the symbols. Use a stable sort to stabilize the output.
485   for (std::pair<const SectionRef, SectionSymbolsTy> &SecSyms : AllSymbols)
486     stable_sort(SecSyms.second);
487 
488   DisassembleFunctionSet.insert(DisassembleFunctions.begin(),
489                                 DisassembleFunctions.end());
490   assert((DisassembleFunctionSet.empty() || ShowDisassemblyOnly) &&
491          "Functions to disassemble should be only specified together with "
492          "--show-disassembly-only");
493 
494   if (ShowDisassemblyOnly)
495     outs() << "\nDisassembly of " << FileName << ":\n";
496 
497   // Dissassemble a text section.
498   for (section_iterator SI = Obj->section_begin(), SE = Obj->section_end();
499        SI != SE; ++SI) {
500     const SectionRef &Section = *SI;
501     if (!Section.isText())
502       continue;
503 
504     uint64_t ImageLoadAddr = getPreferredBaseAddress();
505     uint64_t SectionOffset = Section.getAddress() - ImageLoadAddr;
506     uint64_t SectSize = Section.getSize();
507     if (!SectSize)
508       continue;
509 
510     // Register the text section.
511     TextSections.insert({SectionOffset, SectSize});
512 
513     if (ShowDisassemblyOnly) {
514       StringRef SectionName = unwrapOrError(Section.getName(), FileName);
515       outs() << "\nDisassembly of section " << SectionName;
516       outs() << " [" << format("0x%" PRIx64, Section.getAddress()) << ", "
517              << format("0x%" PRIx64, Section.getAddress() + SectSize)
518              << "]:\n\n";
519     }
520 
521     // Get the section data.
522     ArrayRef<uint8_t> Bytes =
523         arrayRefFromStringRef(unwrapOrError(Section.getContents(), FileName));
524 
525     // Get the list of all the symbols in this section.
526     SectionSymbolsTy &Symbols = AllSymbols[Section];
527 
528     // Disassemble symbol by symbol.
529     for (std::size_t SI = 0, SE = Symbols.size(); SI != SE; ++SI) {
530       if (!dissassembleSymbol(SI, Bytes, Symbols, Section))
531         exitWithError("disassembling error", FileName);
532     }
533   }
534 }
535 
536 void ProfiledBinary::loadSymbolsFromDWARF(ObjectFile &Obj) {
537   auto DebugContext = llvm::DWARFContext::create(Obj);
538   if (!DebugContext)
539     exitWithError("Misssing debug info.", Path);
540 
541   for (const auto &CompilationUnit : DebugContext->compile_units()) {
542     for (const auto &DieInfo : CompilationUnit->dies()) {
543       llvm::DWARFDie Die(CompilationUnit.get(), &DieInfo);
544 
545       if (!Die.isSubprogramDIE())
546         continue;
547       auto Name = Die.getName(llvm::DINameKind::LinkageName);
548       if (!Name)
549         Name = Die.getName(llvm::DINameKind::ShortName);
550       if (!Name)
551         continue;
552 
553       auto RangesOrError = Die.getAddressRanges();
554       if (!RangesOrError)
555         continue;
556       const DWARFAddressRangesVector &Ranges = RangesOrError.get();
557 
558       if (Ranges.empty())
559         continue;
560 
561       // Different DWARF symbols can have same function name, search or create
562       // BinaryFunction indexed by the name.
563       auto Ret = BinaryFunctions.emplace(Name, BinaryFunction());
564       auto &Func = Ret.first->second;
565       if (Ret.second)
566         Func.FuncName = Ret.first->first;
567 
568       for (const auto &Range : Ranges) {
569         uint64_t FuncStart = Range.LowPC;
570         uint64_t FuncSize = Range.HighPC - FuncStart;
571 
572         if (FuncSize == 0 || FuncStart < getPreferredBaseAddress())
573           continue;
574 
575         uint64_t StartOffset = FuncStart - getPreferredBaseAddress();
576         uint64_t EndOffset = Range.HighPC - getPreferredBaseAddress();
577 
578         // We may want to know all ranges for one function. Here group the
579         // ranges and store them into BinaryFunction.
580         Func.Ranges.emplace_back(StartOffset, EndOffset);
581 
582         auto R = StartOffset2FuncRangeMap.emplace(StartOffset, FuncRange());
583         if (R.second) {
584           FuncRange &FRange = R.first->second;
585           FRange.Func = &Func;
586           FRange.StartOffset = StartOffset;
587           FRange.EndOffset = EndOffset;
588         } else {
589           WithColor::warning()
590               << "Duplicated symbol start address at "
591               << format("%8" PRIx64, StartOffset + getPreferredBaseAddress())
592               << " " << R.first->second.getFuncName() << " and " << Name
593               << "\n";
594         }
595       }
596     }
597   }
598   assert(!StartOffset2FuncRangeMap.empty() && "Misssing debug info.");
599 }
600 
601 void ProfiledBinary::populateSymbolListFromDWARF(
602     ProfileSymbolList &SymbolList) {
603   for (auto &I : StartOffset2FuncRangeMap)
604     SymbolList.add(I.second.getFuncName());
605 }
606 
607 void ProfiledBinary::setupSymbolizer() {
608   symbolize::LLVMSymbolizer::Options SymbolizerOpts;
609   SymbolizerOpts.PrintFunctions =
610       DILineInfoSpecifier::FunctionNameKind::LinkageName;
611   SymbolizerOpts.Demangle = false;
612   SymbolizerOpts.DefaultArch = TheTriple.getArchName().str();
613   SymbolizerOpts.UseSymbolTable = false;
614   SymbolizerOpts.RelativeAddresses = false;
615   Symbolizer = std::make_unique<symbolize::LLVMSymbolizer>(SymbolizerOpts);
616 }
617 
618 SampleContextFrameVector ProfiledBinary::symbolize(const InstructionPointer &IP,
619                                                    bool UseCanonicalFnName,
620                                                    bool UseProbeDiscriminator) {
621   assert(this == IP.Binary &&
622          "Binary should only symbolize its own instruction");
623   auto Addr = object::SectionedAddress{IP.Offset + getPreferredBaseAddress(),
624                                        object::SectionedAddress::UndefSection};
625   DIInliningInfo InlineStack =
626       unwrapOrError(Symbolizer->symbolizeInlinedCode(Path, Addr), getName());
627 
628   SampleContextFrameVector CallStack;
629   for (int32_t I = InlineStack.getNumberOfFrames() - 1; I >= 0; I--) {
630     const auto &CallerFrame = InlineStack.getFrame(I);
631     if (CallerFrame.FunctionName == "<invalid>")
632       break;
633 
634     StringRef FunctionName(CallerFrame.FunctionName);
635     if (UseCanonicalFnName)
636       FunctionName = FunctionSamples::getCanonicalFnName(FunctionName);
637 
638     uint32_t Discriminator = CallerFrame.Discriminator;
639     uint32_t LineOffset = CallerFrame.Line - CallerFrame.StartLine;
640     if (UseProbeDiscriminator) {
641       LineOffset =
642           PseudoProbeDwarfDiscriminator::extractProbeIndex(Discriminator);
643       Discriminator = 0;
644     } else {
645       // Filter out invalid negative(int type) lineOffset
646       if (LineOffset & 0xffff0000)
647         return SampleContextFrameVector();
648     }
649 
650     LineLocation Line(LineOffset, Discriminator);
651     auto It = NameStrings.insert(FunctionName.str());
652     CallStack.emplace_back(*It.first, Line);
653   }
654 
655   return CallStack;
656 }
657 
658 void ProfiledBinary::computeInlinedContextSizeForRange(uint64_t StartOffset,
659                                                        uint64_t EndOffset) {
660   uint64_t RangeBegin = offsetToVirtualAddr(StartOffset);
661   uint64_t RangeEnd = offsetToVirtualAddr(EndOffset);
662   InstructionPointer IP(this, RangeBegin, true);
663 
664   if (IP.Address != RangeBegin)
665     WithColor::warning() << "Invalid start instruction at "
666                          << format("%8" PRIx64, RangeBegin) << "\n";
667 
668   if (IP.Address >= RangeEnd)
669     return;
670 
671   do {
672     uint64_t Offset = virtualAddrToOffset(IP.Address);
673     const SampleContextFrameVector &SymbolizedCallStack =
674         getFrameLocationStack(Offset, UsePseudoProbes);
675     uint64_t Size = Offset2InstSizeMap[Offset];
676 
677     // Record instruction size for the corresponding context
678     FuncSizeTracker.addInstructionForContext(SymbolizedCallStack, Size);
679 
680   } while (IP.advance() && IP.Address < RangeEnd);
681 }
682 
683 InstructionPointer::InstructionPointer(const ProfiledBinary *Binary,
684                                        uint64_t Address, bool RoundToNext)
685     : Binary(Binary), Address(Address) {
686   Index = Binary->getIndexForAddr(Address);
687   if (RoundToNext) {
688     // we might get address which is not the code
689     // it should round to the next valid address
690     if (Index >= Binary->getCodeOffsetsSize())
691       this->Address = UINT64_MAX;
692     else
693       this->Address = Binary->getAddressforIndex(Index);
694   }
695 }
696 
697 bool InstructionPointer::advance() {
698   Index++;
699   if (Index >= Binary->getCodeOffsetsSize()) {
700     Address = UINT64_MAX;
701     return false;
702   }
703   Address = Binary->getAddressforIndex(Index);
704   return true;
705 }
706 
707 bool InstructionPointer::backward() {
708   if (Index == 0) {
709     Address = 0;
710     return false;
711   }
712   Index--;
713   Address = Binary->getAddressforIndex(Index);
714   return true;
715 }
716 
717 void InstructionPointer::update(uint64_t Addr) {
718   Address = Addr;
719   Index = Binary->getIndexForAddr(Address);
720 }
721 
722 } // end namespace sampleprof
723 } // end namespace llvm
724