Using address range map to speedup finding inline stack for address.

[danielcdh]

Summary

In the current implementation, to find inline stack for an address incurs expensive linear search in 2 places:

• linear search for the top-level DIE
• recursive linear traverse the DIE tree to find the path to the leaf DIE

In this patch, a map is built from address to its corresponding leaf DIE. The inline stack is built by traversing from the leaf DIE up to the root DIE. This speeds up batch symbolization by ~10X without noticible memory overhead.

[dblaikie]

include/llvm/DebugInfo/DWARF/DWARFUnit.h

140

Would llvm::IntervalMap be more suitable here? (or at least DenseMap, perhaps)

[danielcdh]

include/llvm/DebugInfo/DWARF/DWARFUnit.h

140

They did not provide upper_bound method.

[danielcdh]

update with more comments.

As discussed offline. IntervalMap does not support range splitting, which will be non-trivial to implement. So we still use std:map for the address lookup in AddrDieMap.

[dblaikie]

lib/DebugInfo/DWARF/DWARFUnit.cpp

345–381

It looks like this changes the implementation - getSubprogramForAddress only ever returns subprogram DIEs (so no need for recursing down through children, nor for splitting ranges), but the address map contains both subprogram and inlined subroutine DIEs. Seems like a change in behavior - if intentional, that would warrant some tests to demonstrate the new behavior.

361

Probably more important to explain why this is done, rather than the fact it is done (the fact is mostly evident from the code, the motivation less-so). (I take it it's done this way to simplify the implementation - so that child ranges overwrite parent ranges - rather than having to implement a non-overriding splitting form for parent ranges to not stomp on child ranges)

362–365

I think these 3 lines can be replaced with:

updateAddressDieMap(getUnitDIE());

Probably?

397–401

What's this change for?

Ah, I guess this is the other half of the changed contract of getSubprogramForAddress?

Perhaps it'd be good to rename getSubprogramForAddress to getSubroutineForAddress to reflect the change in semantics (& check all the existing callers are OK with that)?

[danielcdh]

update

[danielcdh]

lib/DebugInfo/DWARF/DWARFUnit.cpp

345–381

It does not change the behavior.

function name updated to make it clearer.

Also updated the implementation to make sure high addresses are filtered so that the behavior does not change.

397–401

That's correct. Function name updated.

[danielcdh]

update comment

[dblaikie]

"Also updated the implementation to make sure high addresses are filtered so that the behavior does not change." - might be worth having some test coverage there, if it wasn't already present?

lib/DebugInfo/DWARF/DWARFUnit.cpp

375

I'm guessing this should be "std::prev(R)" not "--R" (so as not to modify "R" so that the later return isn't tainted by this modification) - so that this doesn't make the "return R->second.second" produce the wrong answer?

Is it possible to test this path to make sure the behavior is correct once this is fixed?

[danielcdh]

update

[danielcdh]

remove unintended change...

lib/DebugInfo/DWARF/DWARFUnit.cpp

375

This actually dead code as the conditional will always be false. Added assertion there.

Also added the comment to clarify that --R is intended.

[danielcdh]

hold on... the assertion actually triggers... looking into why...

[danielcdh]

update the code to ignore 0-sized ranges.

[danielcdh]

Now the assertion is enabled to ensure the behavior does not change. PTAL. Thanks!

[dblaikie]

Looks good - commit when ready :)

[danielcdh]

Reverted as this breaks buildbot: http://lab.llvm.org:8011/builders/clang-x86_64-debian-fast/builds/3369

[danielcdh]

Updated the logic and remove the assertion. Add a unittest to cover the symbolization of the padding zone.

[dblaikie]

Looks good - some optional bits & pieces. (the else-after-return should be fixed before committing, the others are just FYI in case they appeal to you)

lib/DebugInfo/DWARF/DWARFUnit.cpp

381–382

Avoid "else after return" ( http://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return )

For short cases like this I'm always undecided about whether to put the 'failure' case early or the otehr way around. But I'd probably end up with:

if (Address >= R->second.first)
  return DWARFDie();
return R->second.second;

388–394

& while I'm suggesting changes (again, probably best, if you think they're a good idea, to commit these separately):

parseDWO();
DWARFDie SubroutineDIE = (DWO ? DWO->getUnit() : this)->getSubroutineForAddress(Address);

(both reducing the scope of the SubroutineDIE variable, and removing the duplication in the if/else branches)

403

Not related to your patch, but this 'clear()' looks suspect - since the other side of this if/else adds things to InlinedChain unconditionally (without clearing first) - it seems it must be an invariant of this function that it be called with InlinedChain empty to begin with.

If you like, you could remove this line, add an "assert(InlinedChain.empty())" at the start of the function, then you could reduce the indentation of the code you've added by using a simpler early exit:

if (!SubroutineDIE)
  return;
while (SubroutineDIE) {
  ...

(but could be a follow-up commit (no need to send it for review first) for clarity/separation of concerns)

[danielcdh]

Will have separate patch to address other concerns.

[danielcdh]

update

[danielcdh]

updated in NFC commit r300753.

include/llvm/DebugInfo/DWARF/DWARFDie.h

public:
   /// DW_AT_call_line attribute in this DIE.
   /// \param CallColumn filled in with non-zero if successful, zero if there is
   /// no DW_AT_call_column attribute in this DIE.
   /// \param CallDiscriminator filled in with non-zero if successful, zero if
   /// there is no DW_AT_GNU_discriminator attribute in this DIE.
   void getCallerFrame(uint32_t &CallFile, uint32_t &CallLine,
                       uint32_t &CallColumn, uint32_t &CallDiscriminator) const;
   
-  /// Get inlined chain for a given address, rooted at the current DIE.
-  /// Returns empty chain if address is not contained in address range
-  /// of current DIE.
-  void
-  getInlinedChainForAddress(const uint64_t Address,
-                            SmallVectorImpl<DWARFDie> &InlinedChain) const;
-
   class attribute_iterator;
 
   /// Get an iterator range to all attributes in the current DIE only.
   ///
   /// \returns an iterator range for the attributes of the current DIE.
   iterator_range<attribute_iterator> attributes() const;
   
   class iterator;

include/llvm/DebugInfo/DWARF/DWARFUnit.h

 #include "llvm/Support/DataExtractor.h"
 #include "llvm/Support/Dwarf.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <memory>
 #include <vector>
+#include <map>
 
 namespace llvm {
 
 class DWARFAbbreviationDeclarationSet;
 class DWARFContext;
 class DWARFDebugAbbrev;
 class DWARFUnit;
 
class DWARFUnit {
   uint32_t Length;
   const DWARFAbbreviationDeclarationSet *Abbrevs;
   uint16_t Version;
   uint8_t UnitType;
   uint8_t AddrSize;
   uint64_t BaseAddr;
   // The compile unit debug information entry items.
   std::vector<DWARFDebugInfoEntry> DieArray;
+
+  // Map from range's start address to end address and corresponding DIE.
+  // IntervalMap does not support range removal, as a result, we use the
+  // std::map::upper_bound for address range lookup.
+  std::map<uint64_t, std::pair<uint64_t, DWARFDie>> AddrDieMap;
   typedef iterator_range<std::vector<DWARFDebugInfoEntry>::iterator>
       die_iterator_range;
 
   class DWOHolder {
     object::OwningBinary<object::ObjectFile> DWOFile;
     std::unique_ptr<DWARFContext> DWOContext;
     DWARFUnit *DWOU = nullptr;
 
public:
   StringRef getStringSection() const { return StringSection; }
   StringRef getStringOffsetSection() const { return StringOffsetSection; }
 
   void setAddrOffsetSection(StringRef AOS, uint32_t Base) {
     AddrOffsetSection = AOS;
     AddrOffsetSectionBase = Base;
   }
 
+  // Recursively update address to Die map.
+  void updateAddressDieMap(DWARFDie Die);
+
   void setRangesSection(StringRef RS, uint32_t Base) {
     RangeSection = RS;
     RangeSectionBase = Base;
   }
 
   bool getAddrOffsetSectionItem(uint32_t Index, uint64_t &Result) const;
   // FIXME: Result should be uint64_t in DWARF64.
   bool getStringOffsetSectionItem(uint32_t Index, uint32_t &Result) const;
private:
 
   /// clearDIEs - Clear parsed DIEs to keep memory usage low.
   void clearDIEs(bool KeepCUDie);
 
   /// parseDWO - Parses .dwo file for current compile unit. Returns true if
   /// it was actually constructed.
   bool parseDWO();
 
-  /// getSubprogramForAddress - Returns subprogram DIE with address range
+  /// getSubroutineForAddress - Returns subprogram DIE with address range
   /// encompassing the provided address. The pointer is alive as long as parsed
   /// compile unit DIEs are not cleared.
-  DWARFDie getSubprogramForAddress(uint64_t Address);
+  DWARFDie getSubroutineForAddress(uint64_t Address);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_DWARF_DWARFUNIT_H

lib/DebugInfo/DWARF/DWARFDie.cpp

if (abbrCode) {
         << abbrCode << '\n';
       }
     } else {
       OS.indent(Indent) << "NULL\n";
     }
   }
 }
 
-void DWARFDie::getInlinedChainForAddress(
-    const uint64_t Address, SmallVectorImpl<DWARFDie> &InlinedChain) const {
-  if (isNULL())
-    return;
-  DWARFDie DIE(*this);
-  while (DIE) {
-    // Append current DIE to inlined chain only if it has correct tag
-    // (e.g. it is not a lexical block).
-    if (DIE.isSubroutineDIE())
-      InlinedChain.push_back(DIE);
-
-    // Try to get child which also contains provided address.
-    DWARFDie Child = DIE.getFirstChild();
-    while (Child) {
-      if (Child.addressRangeContainsAddress(Address)) {
-        // Assume there is only one such child.
-        break;
-      }
-      Child = Child.getSibling();
-    }
-    DIE = Child;
-  }
-  // Reverse the obtained chain to make the root of inlined chain last.
-  std::reverse(InlinedChain.begin(), InlinedChain.end());
-}
-
 DWARFDie DWARFDie::getParent() const {
   if (isValid())
     return U->getParent(Die);
   return DWARFDie();
 }
 
 DWARFDie DWARFDie::getSibling() const {
   if (isValid())

lib/DebugInfo/DWARF/DWARFUnit.cpp

void DWARFUnit::collectAddressRanges(DWARFAddressRangesVector &CURanges) {
   if (DWOCreated)
     DWO.reset();
 
   // Keep memory down by clearing DIEs if this generate function
   // caused them to be parsed.
   if (ClearDIEs)
     clearDIEs(true);
 }
 
-DWARFDie
-DWARFUnit::getSubprogramForAddress(uint64_t Address) {
-  extractDIEsIfNeeded(false);
-  for (const DWARFDebugInfoEntry &D : DieArray) {
-    DWARFDie DIE(this, &D);
-    if (DIE.isSubprogramDIE() &&
-        DIE.addressRangeContainsAddress(Address)) {
-      return DIE;
-    }
-  }
+void DWARFUnit::updateAddressDieMap(DWARFDie Die) {
+  if (Die.isSubroutineDIE()) {
+    for (const auto &R : Die.getAddressRanges()) {
+      auto B = AddrDieMap.upper_bound(R.first);
+      if (B != AddrDieMap.begin() && R.first < (--B)->second.first) {
+        // The range is a sub-range of existing ranges, we need to split the
+        // existing range.
+        if (R.second < B->second.first)
+          AddrDieMap[R.second] = B->second;
+        if (R.first > B->first)
+          AddrDieMap[B->first].first = R.first;
+      }
+      AddrDieMap[R.first] = std::make_pair(R.second, Die);
+    }
+  }
+  // Parent DIEs are added to the AddrDieMap prior to the Children DIEs to
+  // simplify the logic to update AddrDieMap. The child's range will always
+  // be equal or smaller than the parent's range. With this assumption, when
+  // adding one range into the map, it will at most split a range into 3
+  // sub-ranges.
+  for (DWARFDie Child = Die.getFirstChild(); Child; Child = Child.getSibling())
+    updateAddressDieMap(Child);
+
+DWARFDie DWARFUnit::getSubroutineForAddress(uint64_t Address) {
+  extractDIEsIfNeeded(false);
+  if (AddrDieMap.empty())
+    updateAddressDieMap(getUnitDIE());
+  auto R = AddrDieMap.upper_bound(Address);
+  if (R == AddrDieMap.begin())
     return DWARFDie();
+  // upper_bound's previous item contains Address.
+  --R;
+  assert(Address < R->second.first);
+  return R->second.second;
 }
 
 void
 DWARFUnit::getInlinedChainForAddress(uint64_t Address,
                                      SmallVectorImpl<DWARFDie> &InlinedChain) {
-  // First, find a subprogram that contains the given address (the root
+  // First, find the subroutine that contains the given address (the leaf
   // of inlined chain).
-  DWARFDie SubprogramDIE;
+  DWARFDie SubroutineDIE;
   // Try to look for subprogram DIEs in the DWO file.
   parseDWO();
   if (DWO)
-    SubprogramDIE = DWO->getUnit()->getSubprogramForAddress(Address);
+    SubroutineDIE = DWO->getUnit()->getSubroutineForAddress(Address);
   else
-    SubprogramDIE = getSubprogramForAddress(Address);
+    SubroutineDIE = getSubroutineForAddress(Address);
 
-  // Get inlined chain rooted at this subprogram DIE.
-  if (SubprogramDIE)
-    SubprogramDIE.getInlinedChainForAddress(Address, InlinedChain);
-  else
+  if (SubroutineDIE) {
+    while (SubroutineDIE) {
+      if (SubroutineDIE.isSubroutineDIE())
+        InlinedChain.push_back(SubroutineDIE);
+      SubroutineDIE  = SubroutineDIE.getParent();
+    }
+  } else
     InlinedChain.clear();
 }
 
 const DWARFUnitIndex &llvm::getDWARFUnitIndex(DWARFContext &Context,
                                               DWARFSectionKind Kind) {
   if (Kind == DW_SECT_INFO)
     return Context.getCUIndex();
   assert(Kind == DW_SECT_TYPES);
   return Context.getTUIndex();

test/tools/llvm-symbolizer/Inputs/discrim.inp

 some text
 0x400590
 0x4005a5
 0x4005ad
 0x4005b9
 0x4005ce
 0x4005d4
+0x4005e5
 some more text