xref: /freebsd-src/contrib/llvm-project/llvm/tools/llvm-dwarfdump/Statistics.cpp (revision 5e801ac66d24704442eba426ed13c3effb8a34e7)
1 //===-- Statistics.cpp - Debug Info quality metrics -----------------------===//
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 "llvm-dwarfdump.h"
10 #include "llvm/ADT/DenseMap.h"
11 #include "llvm/ADT/StringSet.h"
12 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
13 #include "llvm/DebugInfo/DWARF/DWARFDebugLoc.h"
14 #include "llvm/Object/ObjectFile.h"
15 #include "llvm/Support/JSON.h"
16 
17 #define DEBUG_TYPE "dwarfdump"
18 using namespace llvm;
19 using namespace llvm::dwarfdump;
20 using namespace llvm::object;
21 
22 namespace {
23 /// This represents the number of categories of debug location coverage being
24 /// calculated. The first category is the number of variables with 0% location
25 /// coverage, but the last category is the number of variables with 100%
26 /// location coverage.
27 constexpr int NumOfCoverageCategories = 12;
28 
29 /// This is used for zero location coverage bucket.
30 constexpr unsigned ZeroCoverageBucket = 0;
31 
32 /// The UINT64_MAX is used as an indication of the overflow.
33 constexpr uint64_t OverflowValue = std::numeric_limits<uint64_t>::max();
34 
35 /// This represents variables DIE offsets.
36 using AbstractOriginVarsTy = llvm::SmallVector<uint64_t>;
37 /// This maps function DIE offset to its variables.
38 using AbstractOriginVarsTyMap = llvm::DenseMap<uint64_t, AbstractOriginVarsTy>;
39 /// This represents function DIE offsets containing an abstract_origin.
40 using FunctionsWithAbstractOriginTy = llvm::SmallVector<uint64_t>;
41 
42 /// This represents a data type for the stats and it helps us to
43 /// detect an overflow.
44 /// NOTE: This can be implemented as a template if there is an another type
45 /// needing this.
46 struct SaturatingUINT64 {
47   /// Number that represents the stats.
48   uint64_t Value;
49 
50   SaturatingUINT64(uint64_t Value_) : Value(Value_) {}
51 
52   void operator++(int) { return *this += 1; }
53   void operator+=(uint64_t Value_) {
54     if (Value != OverflowValue) {
55       if (Value < OverflowValue - Value_)
56         Value += Value_;
57       else
58         Value = OverflowValue;
59     }
60   }
61 };
62 
63 /// Holds statistics for one function (or other entity that has a PC range and
64 /// contains variables, such as a compile unit).
65 struct PerFunctionStats {
66   /// Number of inlined instances of this function.
67   uint64_t NumFnInlined = 0;
68   /// Number of out-of-line instances of this function.
69   uint64_t NumFnOutOfLine = 0;
70   /// Number of inlined instances that have abstract origins.
71   uint64_t NumAbstractOrigins = 0;
72   /// Number of variables and parameters with location across all inlined
73   /// instances.
74   uint64_t TotalVarWithLoc = 0;
75   /// Number of constants with location across all inlined instances.
76   uint64_t ConstantMembers = 0;
77   /// Number of arificial variables, parameters or members across all instances.
78   uint64_t NumArtificial = 0;
79   /// List of all Variables and parameters in this function.
80   StringSet<> VarsInFunction;
81   /// Compile units also cover a PC range, but have this flag set to false.
82   bool IsFunction = false;
83   /// Function has source location information.
84   bool HasSourceLocation = false;
85   /// Number of function parameters.
86   uint64_t NumParams = 0;
87   /// Number of function parameters with source location.
88   uint64_t NumParamSourceLocations = 0;
89   /// Number of function parameters with type.
90   uint64_t NumParamTypes = 0;
91   /// Number of function parameters with a DW_AT_location.
92   uint64_t NumParamLocations = 0;
93   /// Number of local variables.
94   uint64_t NumLocalVars = 0;
95   /// Number of local variables with source location.
96   uint64_t NumLocalVarSourceLocations = 0;
97   /// Number of local variables with type.
98   uint64_t NumLocalVarTypes = 0;
99   /// Number of local variables with DW_AT_location.
100   uint64_t NumLocalVarLocations = 0;
101 };
102 
103 /// Holds accumulated global statistics about DIEs.
104 struct GlobalStats {
105   /// Total number of PC range bytes covered by DW_AT_locations.
106   SaturatingUINT64 TotalBytesCovered = 0;
107   /// Total number of parent DIE PC range bytes covered by DW_AT_Locations.
108   SaturatingUINT64 ScopeBytesCovered = 0;
109   /// Total number of PC range bytes in each variable's enclosing scope.
110   SaturatingUINT64 ScopeBytes = 0;
111   /// Total number of PC range bytes covered by DW_AT_locations with
112   /// the debug entry values (DW_OP_entry_value).
113   SaturatingUINT64 ScopeEntryValueBytesCovered = 0;
114   /// Total number of PC range bytes covered by DW_AT_locations of
115   /// formal parameters.
116   SaturatingUINT64 ParamScopeBytesCovered = 0;
117   /// Total number of PC range bytes in each parameter's enclosing scope.
118   SaturatingUINT64 ParamScopeBytes = 0;
119   /// Total number of PC range bytes covered by DW_AT_locations with
120   /// the debug entry values (DW_OP_entry_value) (only for parameters).
121   SaturatingUINT64 ParamScopeEntryValueBytesCovered = 0;
122   /// Total number of PC range bytes covered by DW_AT_locations (only for local
123   /// variables).
124   SaturatingUINT64 LocalVarScopeBytesCovered = 0;
125   /// Total number of PC range bytes in each local variable's enclosing scope.
126   SaturatingUINT64 LocalVarScopeBytes = 0;
127   /// Total number of PC range bytes covered by DW_AT_locations with
128   /// the debug entry values (DW_OP_entry_value) (only for local variables).
129   SaturatingUINT64 LocalVarScopeEntryValueBytesCovered = 0;
130   /// Total number of call site entries (DW_AT_call_file & DW_AT_call_line).
131   SaturatingUINT64 CallSiteEntries = 0;
132   /// Total number of call site DIEs (DW_TAG_call_site).
133   SaturatingUINT64 CallSiteDIEs = 0;
134   /// Total number of call site parameter DIEs (DW_TAG_call_site_parameter).
135   SaturatingUINT64 CallSiteParamDIEs = 0;
136   /// Total byte size of concrete functions. This byte size includes
137   /// inline functions contained in the concrete functions.
138   SaturatingUINT64 FunctionSize = 0;
139   /// Total byte size of inlined functions. This is the total number of bytes
140   /// for the top inline functions within concrete functions. This can help
141   /// tune the inline settings when compiling to match user expectations.
142   SaturatingUINT64 InlineFunctionSize = 0;
143 };
144 
145 /// Holds accumulated debug location statistics about local variables and
146 /// formal parameters.
147 struct LocationStats {
148   /// Map the scope coverage decile to the number of variables in the decile.
149   /// The first element of the array (at the index zero) represents the number
150   /// of variables with the no debug location at all, but the last element
151   /// in the vector represents the number of fully covered variables within
152   /// its scope.
153   std::vector<SaturatingUINT64> VarParamLocStats{
154       std::vector<SaturatingUINT64>(NumOfCoverageCategories, 0)};
155   /// Map non debug entry values coverage.
156   std::vector<SaturatingUINT64> VarParamNonEntryValLocStats{
157       std::vector<SaturatingUINT64>(NumOfCoverageCategories, 0)};
158   /// The debug location statistics for formal parameters.
159   std::vector<SaturatingUINT64> ParamLocStats{
160       std::vector<SaturatingUINT64>(NumOfCoverageCategories, 0)};
161   /// Map non debug entry values coverage for formal parameters.
162   std::vector<SaturatingUINT64> ParamNonEntryValLocStats{
163       std::vector<SaturatingUINT64>(NumOfCoverageCategories, 0)};
164   /// The debug location statistics for local variables.
165   std::vector<SaturatingUINT64> LocalVarLocStats{
166       std::vector<SaturatingUINT64>(NumOfCoverageCategories, 0)};
167   /// Map non debug entry values coverage for local variables.
168   std::vector<SaturatingUINT64> LocalVarNonEntryValLocStats{
169       std::vector<SaturatingUINT64>(NumOfCoverageCategories, 0)};
170   /// Total number of local variables and function parameters processed.
171   SaturatingUINT64 NumVarParam = 0;
172   /// Total number of formal parameters processed.
173   SaturatingUINT64 NumParam = 0;
174   /// Total number of local variables processed.
175   SaturatingUINT64 NumVar = 0;
176 };
177 } // namespace
178 
179 /// Collect debug location statistics for one DIE.
180 static void collectLocStats(uint64_t ScopeBytesCovered, uint64_t BytesInScope,
181                             std::vector<SaturatingUINT64> &VarParamLocStats,
182                             std::vector<SaturatingUINT64> &ParamLocStats,
183                             std::vector<SaturatingUINT64> &LocalVarLocStats,
184                             bool IsParam, bool IsLocalVar) {
185   auto getCoverageBucket = [ScopeBytesCovered, BytesInScope]() -> unsigned {
186     // No debug location at all for the variable.
187     if (ScopeBytesCovered == 0)
188       return 0;
189     // Fully covered variable within its scope.
190     if (ScopeBytesCovered >= BytesInScope)
191       return NumOfCoverageCategories - 1;
192     // Get covered range (e.g. 20%-29%).
193     unsigned LocBucket = 100 * (double)ScopeBytesCovered / BytesInScope;
194     LocBucket /= 10;
195     return LocBucket + 1;
196   };
197 
198   unsigned CoverageBucket = getCoverageBucket();
199 
200   VarParamLocStats[CoverageBucket].Value++;
201   if (IsParam)
202     ParamLocStats[CoverageBucket].Value++;
203   else if (IsLocalVar)
204     LocalVarLocStats[CoverageBucket].Value++;
205 }
206 
207 /// Construct an identifier for a given DIE from its Prefix, Name, DeclFileName
208 /// and DeclLine. The identifier aims to be unique for any unique entities,
209 /// but keeping the same among different instances of the same entity.
210 static std::string constructDieID(DWARFDie Die,
211                                   StringRef Prefix = StringRef()) {
212   std::string IDStr;
213   llvm::raw_string_ostream ID(IDStr);
214   ID << Prefix
215      << Die.getName(DINameKind::LinkageName);
216 
217   // Prefix + Name is enough for local variables and parameters.
218   if (!Prefix.empty() && !Prefix.equals("g"))
219     return ID.str();
220 
221   auto DeclFile = Die.findRecursively(dwarf::DW_AT_decl_file);
222   std::string File;
223   if (DeclFile) {
224     DWARFUnit *U = Die.getDwarfUnit();
225     if (const auto *LT = U->getContext().getLineTableForUnit(U))
226       if (LT->getFileNameByIndex(
227               dwarf::toUnsigned(DeclFile, 0), U->getCompilationDir(),
228               DILineInfoSpecifier::FileLineInfoKind::AbsoluteFilePath, File))
229         File = std::string(sys::path::filename(File));
230   }
231   ID << ":" << (File.empty() ? "/" : File);
232   ID << ":"
233      << dwarf::toUnsigned(Die.findRecursively(dwarf::DW_AT_decl_line), 0);
234   return ID.str();
235 }
236 
237 /// Return the number of bytes in the overlap of ranges A and B.
238 static uint64_t calculateOverlap(DWARFAddressRange A, DWARFAddressRange B) {
239   uint64_t Lower = std::max(A.LowPC, B.LowPC);
240   uint64_t Upper = std::min(A.HighPC, B.HighPC);
241   if (Lower >= Upper)
242     return 0;
243   return Upper - Lower;
244 }
245 
246 /// Collect debug info quality metrics for one DIE.
247 static void collectStatsForDie(DWARFDie Die, const std::string &FnPrefix,
248                                const std::string &VarPrefix,
249                                uint64_t BytesInScope, uint32_t InlineDepth,
250                                StringMap<PerFunctionStats> &FnStatMap,
251                                GlobalStats &GlobalStats,
252                                LocationStats &LocStats,
253                                AbstractOriginVarsTy *AbstractOriginVariables) {
254   const dwarf::Tag Tag = Die.getTag();
255   // Skip CU node.
256   if (Tag == dwarf::DW_TAG_compile_unit)
257     return;
258 
259   bool HasLoc = false;
260   bool HasSrcLoc = false;
261   bool HasType = false;
262   uint64_t TotalBytesCovered = 0;
263   uint64_t ScopeBytesCovered = 0;
264   uint64_t BytesEntryValuesCovered = 0;
265   auto &FnStats = FnStatMap[FnPrefix];
266   bool IsParam = Tag == dwarf::DW_TAG_formal_parameter;
267   bool IsLocalVar = Tag == dwarf::DW_TAG_variable;
268   bool IsConstantMember = Tag == dwarf::DW_TAG_member &&
269                           Die.find(dwarf::DW_AT_const_value);
270 
271   // For zero covered inlined variables the locstats will be
272   // calculated later.
273   bool DeferLocStats = false;
274 
275   if (Tag == dwarf::DW_TAG_call_site || Tag == dwarf::DW_TAG_GNU_call_site) {
276     GlobalStats.CallSiteDIEs++;
277     return;
278   }
279 
280   if (Tag == dwarf::DW_TAG_call_site_parameter ||
281       Tag == dwarf::DW_TAG_GNU_call_site_parameter) {
282     GlobalStats.CallSiteParamDIEs++;
283     return;
284   }
285 
286   if (!IsParam && !IsLocalVar && !IsConstantMember) {
287     // Not a variable or constant member.
288     return;
289   }
290 
291   // Ignore declarations of global variables.
292   if (IsLocalVar && Die.find(dwarf::DW_AT_declaration))
293     return;
294 
295   if (Die.findRecursively(dwarf::DW_AT_decl_file) &&
296       Die.findRecursively(dwarf::DW_AT_decl_line))
297     HasSrcLoc = true;
298 
299   if (Die.findRecursively(dwarf::DW_AT_type))
300     HasType = true;
301 
302   if (Die.find(dwarf::DW_AT_abstract_origin)) {
303     if (Die.find(dwarf::DW_AT_location) || Die.find(dwarf::DW_AT_const_value)) {
304       if (AbstractOriginVariables) {
305         auto Offset = Die.find(dwarf::DW_AT_abstract_origin);
306         // Do not track this variable any more, since it has location
307         // coverage.
308         llvm::erase_value(*AbstractOriginVariables, (*Offset).getRawUValue());
309       }
310     } else {
311       // The locstats will be handled at the end of
312       // the collectStatsRecursive().
313       DeferLocStats = true;
314     }
315   }
316 
317   auto IsEntryValue = [&](ArrayRef<uint8_t> D) -> bool {
318     DWARFUnit *U = Die.getDwarfUnit();
319     DataExtractor Data(toStringRef(D),
320                        Die.getDwarfUnit()->getContext().isLittleEndian(), 0);
321     DWARFExpression Expression(Data, U->getAddressByteSize(),
322                                U->getFormParams().Format);
323     // Consider the expression containing the DW_OP_entry_value as
324     // an entry value.
325     return llvm::any_of(Expression, [](const DWARFExpression::Operation &Op) {
326       return Op.getCode() == dwarf::DW_OP_entry_value ||
327              Op.getCode() == dwarf::DW_OP_GNU_entry_value;
328     });
329   };
330 
331   if (Die.find(dwarf::DW_AT_const_value)) {
332     // This catches constant members *and* variables.
333     HasLoc = true;
334     ScopeBytesCovered = BytesInScope;
335     TotalBytesCovered = BytesInScope;
336   } else {
337     // Handle variables and function arguments.
338     Expected<std::vector<DWARFLocationExpression>> Loc =
339         Die.getLocations(dwarf::DW_AT_location);
340     if (!Loc) {
341       consumeError(Loc.takeError());
342     } else {
343       HasLoc = true;
344       // Get PC coverage.
345       auto Default = find_if(
346           *Loc, [](const DWARFLocationExpression &L) { return !L.Range; });
347       if (Default != Loc->end()) {
348         // Assume the entire range is covered by a single location.
349         ScopeBytesCovered = BytesInScope;
350         TotalBytesCovered = BytesInScope;
351       } else {
352         // Caller checks this Expected result already, it cannot fail.
353         auto ScopeRanges = cantFail(Die.getParent().getAddressRanges());
354         for (auto Entry : *Loc) {
355           TotalBytesCovered += Entry.Range->HighPC - Entry.Range->LowPC;
356           uint64_t ScopeBytesCoveredByEntry = 0;
357           // Calculate how many bytes of the parent scope this entry covers.
358           // FIXME: In section 2.6.2 of the DWARFv5 spec it says that "The
359           // address ranges defined by the bounded location descriptions of a
360           // location list may overlap". So in theory a variable can have
361           // multiple simultaneous locations, which would make this calculation
362           // misleading because we will count the overlapped areas
363           // twice. However, clang does not currently emit DWARF like this.
364           for (DWARFAddressRange R : ScopeRanges) {
365             ScopeBytesCoveredByEntry += calculateOverlap(*Entry.Range, R);
366           }
367           ScopeBytesCovered += ScopeBytesCoveredByEntry;
368           if (IsEntryValue(Entry.Expr))
369             BytesEntryValuesCovered += ScopeBytesCoveredByEntry;
370         }
371       }
372     }
373   }
374 
375   // Calculate the debug location statistics.
376   if (BytesInScope && !DeferLocStats) {
377     LocStats.NumVarParam.Value++;
378     if (IsParam)
379       LocStats.NumParam.Value++;
380     else if (IsLocalVar)
381       LocStats.NumVar.Value++;
382 
383     collectLocStats(ScopeBytesCovered, BytesInScope, LocStats.VarParamLocStats,
384                     LocStats.ParamLocStats, LocStats.LocalVarLocStats, IsParam,
385                     IsLocalVar);
386     // Non debug entry values coverage statistics.
387     collectLocStats(ScopeBytesCovered - BytesEntryValuesCovered, BytesInScope,
388                     LocStats.VarParamNonEntryValLocStats,
389                     LocStats.ParamNonEntryValLocStats,
390                     LocStats.LocalVarNonEntryValLocStats, IsParam, IsLocalVar);
391   }
392 
393   // Collect PC range coverage data.
394   if (DWARFDie D =
395           Die.getAttributeValueAsReferencedDie(dwarf::DW_AT_abstract_origin))
396     Die = D;
397 
398   std::string VarID = constructDieID(Die, VarPrefix);
399   FnStats.VarsInFunction.insert(VarID);
400 
401   GlobalStats.TotalBytesCovered += TotalBytesCovered;
402   if (BytesInScope) {
403     GlobalStats.ScopeBytesCovered += ScopeBytesCovered;
404     GlobalStats.ScopeBytes += BytesInScope;
405     GlobalStats.ScopeEntryValueBytesCovered += BytesEntryValuesCovered;
406     if (IsParam) {
407       GlobalStats.ParamScopeBytesCovered += ScopeBytesCovered;
408       GlobalStats.ParamScopeBytes += BytesInScope;
409       GlobalStats.ParamScopeEntryValueBytesCovered += BytesEntryValuesCovered;
410     } else if (IsLocalVar) {
411       GlobalStats.LocalVarScopeBytesCovered += ScopeBytesCovered;
412       GlobalStats.LocalVarScopeBytes += BytesInScope;
413       GlobalStats.LocalVarScopeEntryValueBytesCovered +=
414           BytesEntryValuesCovered;
415     }
416     assert(GlobalStats.ScopeBytesCovered.Value <= GlobalStats.ScopeBytes.Value);
417   }
418 
419   if (IsConstantMember) {
420     FnStats.ConstantMembers++;
421     return;
422   }
423 
424   FnStats.TotalVarWithLoc += (unsigned)HasLoc;
425 
426   if (Die.find(dwarf::DW_AT_artificial)) {
427     FnStats.NumArtificial++;
428     return;
429   }
430 
431   if (IsParam) {
432     FnStats.NumParams++;
433     if (HasType)
434       FnStats.NumParamTypes++;
435     if (HasSrcLoc)
436       FnStats.NumParamSourceLocations++;
437     if (HasLoc)
438       FnStats.NumParamLocations++;
439   } else if (IsLocalVar) {
440     FnStats.NumLocalVars++;
441     if (HasType)
442       FnStats.NumLocalVarTypes++;
443     if (HasSrcLoc)
444       FnStats.NumLocalVarSourceLocations++;
445     if (HasLoc)
446       FnStats.NumLocalVarLocations++;
447   }
448 }
449 
450 /// Recursively collect variables from subprogram with DW_AT_inline attribute.
451 static void collectAbstractOriginFnInfo(
452     DWARFDie Die, uint64_t SPOffset,
453     AbstractOriginVarsTyMap &GlobalAbstractOriginFnInfo) {
454   DWARFDie Child = Die.getFirstChild();
455   while (Child) {
456     const dwarf::Tag ChildTag = Child.getTag();
457     if (ChildTag == dwarf::DW_TAG_formal_parameter ||
458         ChildTag == dwarf::DW_TAG_variable)
459       GlobalAbstractOriginFnInfo[SPOffset].push_back(Child.getOffset());
460     else if (ChildTag == dwarf::DW_TAG_lexical_block)
461       collectAbstractOriginFnInfo(Child, SPOffset, GlobalAbstractOriginFnInfo);
462     Child = Child.getSibling();
463   }
464 }
465 
466 /// Recursively collect debug info quality metrics.
467 static void collectStatsRecursive(
468     DWARFDie Die, std::string FnPrefix, std::string VarPrefix,
469     uint64_t BytesInScope, uint32_t InlineDepth,
470     StringMap<PerFunctionStats> &FnStatMap, GlobalStats &GlobalStats,
471     LocationStats &LocStats,
472     AbstractOriginVarsTyMap &GlobalAbstractOriginFnInfo,
473     FunctionsWithAbstractOriginTy &FnsWithAbstractOriginToBeProcessed,
474     AbstractOriginVarsTy *AbstractOriginVarsPtr = nullptr) {
475   // Skip NULL nodes.
476   if (Die.isNULL())
477     return;
478 
479   const dwarf::Tag Tag = Die.getTag();
480   // Skip function types.
481   if (Tag == dwarf::DW_TAG_subroutine_type)
482     return;
483 
484   // Handle any kind of lexical scope.
485   const bool HasAbstractOrigin = Die.find(dwarf::DW_AT_abstract_origin) != None;
486   const bool IsFunction = Tag == dwarf::DW_TAG_subprogram;
487   const bool IsBlock = Tag == dwarf::DW_TAG_lexical_block;
488   const bool IsInlinedFunction = Tag == dwarf::DW_TAG_inlined_subroutine;
489   // We want to know how many variables (with abstract_origin) don't have
490   // location info.
491   const bool IsCandidateForZeroLocCovTracking =
492       (IsInlinedFunction || (IsFunction && HasAbstractOrigin));
493 
494   AbstractOriginVarsTy AbstractOriginVars;
495 
496   // Get the vars of the inlined fn, so the locstats
497   // reports the missing vars (with coverage 0%).
498   if (IsCandidateForZeroLocCovTracking) {
499     auto OffsetFn = Die.find(dwarf::DW_AT_abstract_origin);
500     if (OffsetFn) {
501       uint64_t OffsetOfInlineFnCopy = (*OffsetFn).getRawUValue();
502       if (GlobalAbstractOriginFnInfo.count(OffsetOfInlineFnCopy)) {
503         AbstractOriginVars = GlobalAbstractOriginFnInfo[OffsetOfInlineFnCopy];
504         AbstractOriginVarsPtr = &AbstractOriginVars;
505       } else {
506         // This means that the DW_AT_inline fn copy is out of order,
507         // so this abstract origin instance will be processed later.
508         FnsWithAbstractOriginToBeProcessed.push_back(Die.getOffset());
509         AbstractOriginVarsPtr = nullptr;
510       }
511     }
512   }
513 
514   if (IsFunction || IsInlinedFunction || IsBlock) {
515     // Reset VarPrefix when entering a new function.
516     if (IsFunction || IsInlinedFunction)
517       VarPrefix = "v";
518 
519     // Ignore forward declarations.
520     if (Die.find(dwarf::DW_AT_declaration))
521       return;
522 
523     // Check for call sites.
524     if (Die.find(dwarf::DW_AT_call_file) && Die.find(dwarf::DW_AT_call_line))
525       GlobalStats.CallSiteEntries++;
526 
527     // PC Ranges.
528     auto RangesOrError = Die.getAddressRanges();
529     if (!RangesOrError) {
530       llvm::consumeError(RangesOrError.takeError());
531       return;
532     }
533 
534     auto Ranges = RangesOrError.get();
535     uint64_t BytesInThisScope = 0;
536     for (auto Range : Ranges)
537       BytesInThisScope += Range.HighPC - Range.LowPC;
538 
539     // Count the function.
540     if (!IsBlock) {
541       // Skip over abstract origins, but collect variables
542       // from it so it can be used for location statistics
543       // for inlined instancies.
544       if (Die.find(dwarf::DW_AT_inline)) {
545         uint64_t SPOffset = Die.getOffset();
546         collectAbstractOriginFnInfo(Die, SPOffset, GlobalAbstractOriginFnInfo);
547         return;
548       }
549 
550       std::string FnID = constructDieID(Die);
551       // We've seen an instance of this function.
552       auto &FnStats = FnStatMap[FnID];
553       FnStats.IsFunction = true;
554       if (IsInlinedFunction) {
555         FnStats.NumFnInlined++;
556         if (Die.findRecursively(dwarf::DW_AT_abstract_origin))
557           FnStats.NumAbstractOrigins++;
558       } else {
559         FnStats.NumFnOutOfLine++;
560       }
561       if (Die.findRecursively(dwarf::DW_AT_decl_file) &&
562           Die.findRecursively(dwarf::DW_AT_decl_line))
563         FnStats.HasSourceLocation = true;
564       // Update function prefix.
565       FnPrefix = FnID;
566     }
567 
568     if (BytesInThisScope) {
569       BytesInScope = BytesInThisScope;
570       if (IsFunction)
571         GlobalStats.FunctionSize += BytesInThisScope;
572       else if (IsInlinedFunction && InlineDepth == 0)
573         GlobalStats.InlineFunctionSize += BytesInThisScope;
574     }
575   } else {
576     // Not a scope, visit the Die itself. It could be a variable.
577     collectStatsForDie(Die, FnPrefix, VarPrefix, BytesInScope, InlineDepth,
578                        FnStatMap, GlobalStats, LocStats, AbstractOriginVarsPtr);
579   }
580 
581   // Set InlineDepth correctly for child recursion
582   if (IsFunction)
583     InlineDepth = 0;
584   else if (IsInlinedFunction)
585     ++InlineDepth;
586 
587   // Traverse children.
588   unsigned LexicalBlockIndex = 0;
589   unsigned FormalParameterIndex = 0;
590   DWARFDie Child = Die.getFirstChild();
591   while (Child) {
592     std::string ChildVarPrefix = VarPrefix;
593     if (Child.getTag() == dwarf::DW_TAG_lexical_block)
594       ChildVarPrefix += toHex(LexicalBlockIndex++) + '.';
595     if (Child.getTag() == dwarf::DW_TAG_formal_parameter)
596       ChildVarPrefix += 'p' + toHex(FormalParameterIndex++) + '.';
597 
598     collectStatsRecursive(
599         Child, FnPrefix, ChildVarPrefix, BytesInScope, InlineDepth, FnStatMap,
600         GlobalStats, LocStats, GlobalAbstractOriginFnInfo,
601         FnsWithAbstractOriginToBeProcessed, AbstractOriginVarsPtr);
602     Child = Child.getSibling();
603   }
604 
605   if (!IsCandidateForZeroLocCovTracking)
606     return;
607 
608   // After we have processed all vars of the inlined function (or function with
609   // an abstract_origin), we want to know how many variables have no location.
610   for (auto Offset : AbstractOriginVars) {
611     LocStats.NumVarParam++;
612     LocStats.VarParamLocStats[ZeroCoverageBucket]++;
613     auto FnDie = Die.getDwarfUnit()->getDIEForOffset(Offset);
614     if (!FnDie)
615       continue;
616     auto Tag = FnDie.getTag();
617     if (Tag == dwarf::DW_TAG_formal_parameter) {
618       LocStats.NumParam++;
619       LocStats.ParamLocStats[ZeroCoverageBucket]++;
620     } else if (Tag == dwarf::DW_TAG_variable) {
621       LocStats.NumVar++;
622       LocStats.LocalVarLocStats[ZeroCoverageBucket]++;
623     }
624   }
625 }
626 
627 /// Print human-readable output.
628 /// \{
629 static void printDatum(json::OStream &J, const char *Key, json::Value Value) {
630   if (Value == OverflowValue)
631     J.attribute(Key, "overflowed");
632   else
633     J.attribute(Key, Value);
634 
635   LLVM_DEBUG(llvm::dbgs() << Key << ": " << Value << '\n');
636 }
637 
638 static void printLocationStats(json::OStream &J, const char *Key,
639                                std::vector<SaturatingUINT64> &LocationStats) {
640   if (LocationStats[0].Value == OverflowValue)
641     J.attribute((Twine(Key) +
642                  " with (0%,10%) of parent scope covered by DW_AT_location")
643                     .str(),
644                 "overflowed");
645   else
646     J.attribute(
647         (Twine(Key) + " with 0% of parent scope covered by DW_AT_location")
648             .str(),
649         LocationStats[0].Value);
650   LLVM_DEBUG(
651       llvm::dbgs() << Key
652                    << " with 0% of parent scope covered by DW_AT_location: \\"
653                    << LocationStats[0].Value << '\n');
654 
655   if (LocationStats[1].Value == OverflowValue)
656     J.attribute((Twine(Key) +
657                  " with (0%,10%) of parent scope covered by DW_AT_location")
658                     .str(),
659                 "overflowed");
660   else
661     J.attribute((Twine(Key) +
662                  " with (0%,10%) of parent scope covered by DW_AT_location")
663                     .str(),
664                 LocationStats[1].Value);
665   LLVM_DEBUG(llvm::dbgs()
666              << Key
667              << " with (0%,10%) of parent scope covered by DW_AT_location: "
668              << LocationStats[1].Value << '\n');
669 
670   for (unsigned i = 2; i < NumOfCoverageCategories - 1; ++i) {
671     if (LocationStats[i].Value == OverflowValue)
672       J.attribute((Twine(Key) + " with [" + Twine((i - 1) * 10) + "%," +
673                    Twine(i * 10) +
674                    "%) of parent scope covered by DW_AT_location")
675                       .str(),
676                   "overflowed");
677     else
678       J.attribute((Twine(Key) + " with [" + Twine((i - 1) * 10) + "%," +
679                    Twine(i * 10) +
680                    "%) of parent scope covered by DW_AT_location")
681                       .str(),
682                   LocationStats[i].Value);
683     LLVM_DEBUG(llvm::dbgs()
684                << Key << " with [" << (i - 1) * 10 << "%," << i * 10
685                << "%) of parent scope covered by DW_AT_location: "
686                << LocationStats[i].Value);
687   }
688   if (LocationStats[NumOfCoverageCategories - 1].Value == OverflowValue)
689     J.attribute(
690         (Twine(Key) + " with 100% of parent scope covered by DW_AT_location")
691             .str(),
692         "overflowed");
693   else
694     J.attribute(
695         (Twine(Key) + " with 100% of parent scope covered by DW_AT_location")
696             .str(),
697         LocationStats[NumOfCoverageCategories - 1].Value);
698   LLVM_DEBUG(
699       llvm::dbgs() << Key
700                    << " with 100% of parent scope covered by DW_AT_location: "
701                    << LocationStats[NumOfCoverageCategories - 1].Value);
702 }
703 
704 static void printSectionSizes(json::OStream &J, const SectionSizes &Sizes) {
705   for (const auto &It : Sizes.DebugSectionSizes)
706     J.attribute((Twine("#bytes in ") + It.first).str(), int64_t(It.second));
707 }
708 
709 /// Stop tracking variables that contain abstract_origin with a location.
710 /// This is used for out-of-order DW_AT_inline subprograms only.
711 static void updateVarsWithAbstractOriginLocCovInfo(
712     DWARFDie FnDieWithAbstractOrigin,
713     AbstractOriginVarsTy &AbstractOriginVars) {
714   DWARFDie Child = FnDieWithAbstractOrigin.getFirstChild();
715   while (Child) {
716     const dwarf::Tag ChildTag = Child.getTag();
717     if ((ChildTag == dwarf::DW_TAG_formal_parameter ||
718          ChildTag == dwarf::DW_TAG_variable) &&
719         (Child.find(dwarf::DW_AT_location) ||
720          Child.find(dwarf::DW_AT_const_value))) {
721       auto OffsetVar = Child.find(dwarf::DW_AT_abstract_origin);
722       if (OffsetVar)
723         llvm::erase_value(AbstractOriginVars, (*OffsetVar).getRawUValue());
724     } else if (ChildTag == dwarf::DW_TAG_lexical_block)
725       updateVarsWithAbstractOriginLocCovInfo(Child, AbstractOriginVars);
726     Child = Child.getSibling();
727   }
728 }
729 
730 /// Collect zero location coverage for inlined variables which refer to
731 /// a DW_AT_inline copy of subprogram that is out of order in the DWARF.
732 /// Also cover the variables of a concrete function (represented with
733 /// the DW_TAG_subprogram) with an abstract_origin attribute.
734 static void collectZeroLocCovForVarsWithAbstractOrigin(
735     DWARFUnit *DwUnit, GlobalStats &GlobalStats, LocationStats &LocStats,
736     AbstractOriginVarsTyMap &GlobalAbstractOriginFnInfo,
737     FunctionsWithAbstractOriginTy &FnsWithAbstractOriginToBeProcessed) {
738   for (auto FnOffset : FnsWithAbstractOriginToBeProcessed) {
739     DWARFDie FnDieWithAbstractOrigin = DwUnit->getDIEForOffset(FnOffset);
740     auto FnCopy = FnDieWithAbstractOrigin.find(dwarf::DW_AT_abstract_origin);
741     AbstractOriginVarsTy AbstractOriginVars;
742     if (!FnCopy)
743       continue;
744 
745     AbstractOriginVars = GlobalAbstractOriginFnInfo[(*FnCopy).getRawUValue()];
746     updateVarsWithAbstractOriginLocCovInfo(FnDieWithAbstractOrigin,
747                                            AbstractOriginVars);
748 
749     for (auto Offset : AbstractOriginVars) {
750       LocStats.NumVarParam++;
751       LocStats.VarParamLocStats[ZeroCoverageBucket]++;
752       auto Tag = DwUnit->getDIEForOffset(Offset).getTag();
753       if (Tag == dwarf::DW_TAG_formal_parameter) {
754         LocStats.NumParam++;
755         LocStats.ParamLocStats[ZeroCoverageBucket]++;
756       } else if (Tag == dwarf::DW_TAG_variable) {
757         LocStats.NumVar++;
758         LocStats.LocalVarLocStats[ZeroCoverageBucket]++;
759       }
760     }
761   }
762 }
763 
764 /// \}
765 
766 /// Collect debug info quality metrics for an entire DIContext.
767 ///
768 /// Do the impossible and reduce the quality of the debug info down to a few
769 /// numbers. The idea is to condense the data into numbers that can be tracked
770 /// over time to identify trends in newer compiler versions and gauge the effect
771 /// of particular optimizations. The raw numbers themselves are not particularly
772 /// useful, only the delta between compiling the same program with different
773 /// compilers is.
774 bool dwarfdump::collectStatsForObjectFile(ObjectFile &Obj, DWARFContext &DICtx,
775                                           const Twine &Filename,
776                                           raw_ostream &OS) {
777   StringRef FormatName = Obj.getFileFormatName();
778   GlobalStats GlobalStats;
779   LocationStats LocStats;
780   StringMap<PerFunctionStats> Statistics;
781   for (const auto &CU : static_cast<DWARFContext *>(&DICtx)->compile_units()) {
782     if (DWARFDie CUDie = CU->getNonSkeletonUnitDIE(false)) {
783       // These variables are being reset for each CU, since there could be
784       // a situation where we have two subprogram DIEs with the same offsets
785       // in two diferent CUs, and we can end up using wrong variables info
786       // when trying to resolve abstract_origin attribute.
787       // TODO: Handle LTO cases where the abstract origin of
788       // the function is in a different CU than the one it's
789       // referenced from or inlined into.
790       AbstractOriginVarsTyMap GlobalAbstractOriginFnInfo;
791       FunctionsWithAbstractOriginTy FnsWithAbstractOriginToBeProcessed;
792 
793       collectStatsRecursive(CUDie, "/", "g", 0, 0, Statistics, GlobalStats,
794                             LocStats, GlobalAbstractOriginFnInfo,
795                             FnsWithAbstractOriginToBeProcessed);
796 
797       collectZeroLocCovForVarsWithAbstractOrigin(
798           CUDie.getDwarfUnit(), GlobalStats, LocStats,
799           GlobalAbstractOriginFnInfo, FnsWithAbstractOriginToBeProcessed);
800     }
801   }
802 
803   /// Collect the sizes of debug sections.
804   SectionSizes Sizes;
805   calculateSectionSizes(Obj, Sizes, Filename);
806 
807   /// The version number should be increased every time the algorithm is changed
808   /// (including bug fixes). New metrics may be added without increasing the
809   /// version.
810   unsigned Version = 9;
811   SaturatingUINT64 VarParamTotal = 0;
812   SaturatingUINT64 VarParamUnique = 0;
813   SaturatingUINT64 VarParamWithLoc = 0;
814   SaturatingUINT64 NumFunctions = 0;
815   SaturatingUINT64 NumInlinedFunctions = 0;
816   SaturatingUINT64 NumFuncsWithSrcLoc = 0;
817   SaturatingUINT64 NumAbstractOrigins = 0;
818   SaturatingUINT64 ParamTotal = 0;
819   SaturatingUINT64 ParamWithType = 0;
820   SaturatingUINT64 ParamWithLoc = 0;
821   SaturatingUINT64 ParamWithSrcLoc = 0;
822   SaturatingUINT64 LocalVarTotal = 0;
823   SaturatingUINT64 LocalVarWithType = 0;
824   SaturatingUINT64 LocalVarWithSrcLoc = 0;
825   SaturatingUINT64 LocalVarWithLoc = 0;
826   for (auto &Entry : Statistics) {
827     PerFunctionStats &Stats = Entry.getValue();
828     uint64_t TotalVars = Stats.VarsInFunction.size() *
829                          (Stats.NumFnInlined + Stats.NumFnOutOfLine);
830     // Count variables in global scope.
831     if (!Stats.IsFunction)
832       TotalVars =
833           Stats.NumLocalVars + Stats.ConstantMembers + Stats.NumArtificial;
834     uint64_t Constants = Stats.ConstantMembers;
835     VarParamWithLoc += Stats.TotalVarWithLoc + Constants;
836     VarParamTotal += TotalVars;
837     VarParamUnique += Stats.VarsInFunction.size();
838     LLVM_DEBUG(for (auto &V
839                     : Stats.VarsInFunction) llvm::dbgs()
840                << Entry.getKey() << ": " << V.getKey() << "\n");
841     NumFunctions += Stats.IsFunction;
842     NumFuncsWithSrcLoc += Stats.HasSourceLocation;
843     NumInlinedFunctions += Stats.IsFunction * Stats.NumFnInlined;
844     NumAbstractOrigins += Stats.IsFunction * Stats.NumAbstractOrigins;
845     ParamTotal += Stats.NumParams;
846     ParamWithType += Stats.NumParamTypes;
847     ParamWithLoc += Stats.NumParamLocations;
848     ParamWithSrcLoc += Stats.NumParamSourceLocations;
849     LocalVarTotal += Stats.NumLocalVars;
850     LocalVarWithType += Stats.NumLocalVarTypes;
851     LocalVarWithLoc += Stats.NumLocalVarLocations;
852     LocalVarWithSrcLoc += Stats.NumLocalVarSourceLocations;
853   }
854 
855   // Print summary.
856   OS.SetBufferSize(1024);
857   json::OStream J(OS, 2);
858   J.objectBegin();
859   J.attribute("version", Version);
860   LLVM_DEBUG(llvm::dbgs() << "Variable location quality metrics\n";
861              llvm::dbgs() << "---------------------------------\n");
862 
863   printDatum(J, "file", Filename.str());
864   printDatum(J, "format", FormatName);
865 
866   printDatum(J, "#functions", NumFunctions.Value);
867   printDatum(J, "#functions with location", NumFuncsWithSrcLoc.Value);
868   printDatum(J, "#inlined functions", NumInlinedFunctions.Value);
869   printDatum(J, "#inlined functions with abstract origins",
870              NumAbstractOrigins.Value);
871 
872   // This includes local variables and formal parameters.
873   printDatum(J, "#unique source variables", VarParamUnique.Value);
874   printDatum(J, "#source variables", VarParamTotal.Value);
875   printDatum(J, "#source variables with location", VarParamWithLoc.Value);
876 
877   printDatum(J, "#call site entries", GlobalStats.CallSiteEntries.Value);
878   printDatum(J, "#call site DIEs", GlobalStats.CallSiteDIEs.Value);
879   printDatum(J, "#call site parameter DIEs",
880              GlobalStats.CallSiteParamDIEs.Value);
881 
882   printDatum(J, "sum_all_variables(#bytes in parent scope)",
883              GlobalStats.ScopeBytes.Value);
884   printDatum(J,
885              "sum_all_variables(#bytes in any scope covered by DW_AT_location)",
886              GlobalStats.TotalBytesCovered.Value);
887   printDatum(J,
888              "sum_all_variables(#bytes in parent scope covered by "
889              "DW_AT_location)",
890              GlobalStats.ScopeBytesCovered.Value);
891   printDatum(J,
892              "sum_all_variables(#bytes in parent scope covered by "
893              "DW_OP_entry_value)",
894              GlobalStats.ScopeEntryValueBytesCovered.Value);
895 
896   printDatum(J, "sum_all_params(#bytes in parent scope)",
897              GlobalStats.ParamScopeBytes.Value);
898   printDatum(J,
899              "sum_all_params(#bytes in parent scope covered by DW_AT_location)",
900              GlobalStats.ParamScopeBytesCovered.Value);
901   printDatum(J,
902              "sum_all_params(#bytes in parent scope covered by "
903              "DW_OP_entry_value)",
904              GlobalStats.ParamScopeEntryValueBytesCovered.Value);
905 
906   printDatum(J, "sum_all_local_vars(#bytes in parent scope)",
907              GlobalStats.LocalVarScopeBytes.Value);
908   printDatum(J,
909              "sum_all_local_vars(#bytes in parent scope covered by "
910              "DW_AT_location)",
911              GlobalStats.LocalVarScopeBytesCovered.Value);
912   printDatum(J,
913              "sum_all_local_vars(#bytes in parent scope covered by "
914              "DW_OP_entry_value)",
915              GlobalStats.LocalVarScopeEntryValueBytesCovered.Value);
916 
917   printDatum(J, "#bytes within functions", GlobalStats.FunctionSize.Value);
918   printDatum(J, "#bytes within inlined functions",
919              GlobalStats.InlineFunctionSize.Value);
920 
921   // Print the summary for formal parameters.
922   printDatum(J, "#params", ParamTotal.Value);
923   printDatum(J, "#params with source location", ParamWithSrcLoc.Value);
924   printDatum(J, "#params with type", ParamWithType.Value);
925   printDatum(J, "#params with binary location", ParamWithLoc.Value);
926 
927   // Print the summary for local variables.
928   printDatum(J, "#local vars", LocalVarTotal.Value);
929   printDatum(J, "#local vars with source location", LocalVarWithSrcLoc.Value);
930   printDatum(J, "#local vars with type", LocalVarWithType.Value);
931   printDatum(J, "#local vars with binary location", LocalVarWithLoc.Value);
932 
933   // Print the debug section sizes.
934   printSectionSizes(J, Sizes);
935 
936   // Print the location statistics for variables (includes local variables
937   // and formal parameters).
938   printDatum(J, "#variables processed by location statistics",
939              LocStats.NumVarParam.Value);
940   printLocationStats(J, "#variables", LocStats.VarParamLocStats);
941   printLocationStats(J, "#variables - entry values",
942                      LocStats.VarParamNonEntryValLocStats);
943 
944   // Print the location statistics for formal parameters.
945   printDatum(J, "#params processed by location statistics",
946              LocStats.NumParam.Value);
947   printLocationStats(J, "#params", LocStats.ParamLocStats);
948   printLocationStats(J, "#params - entry values",
949                      LocStats.ParamNonEntryValLocStats);
950 
951   // Print the location statistics for local variables.
952   printDatum(J, "#local vars processed by location statistics",
953              LocStats.NumVar.Value);
954   printLocationStats(J, "#local vars", LocStats.LocalVarLocStats);
955   printLocationStats(J, "#local vars - entry values",
956                      LocStats.LocalVarNonEntryValLocStats);
957   J.objectEnd();
958   OS << '\n';
959   LLVM_DEBUG(llvm::dbgs() << "Total Availability: "
960                           << (int)std::round((VarParamWithLoc.Value * 100.0) /
961                                              VarParamTotal.Value)
962                           << "%\n";
963              llvm::dbgs() << "PC Ranges covered: "
964                           << (int)std::round(
965                                  (GlobalStats.ScopeBytesCovered.Value * 100.0) /
966                                  GlobalStats.ScopeBytes.Value)
967                           << "%\n");
968   return true;
969 }
970