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

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)

364–372

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.

367–370

I think these 3 lines can be replaced with:

updateAddressDieMap(getUnitDIE());

Probably?

389–393

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

364–372

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.

389–393

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

380

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

380

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

379–385

& 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)

386–387

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;

395

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.
+  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;

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

if (DWOCreated)
     DWO.reset();
 
   // Keep memory down by clearing DIEs if this generate function
   // caused them to be parsed.
   if (ClearDIEs)
     clearDIEs(true);
 }
 
+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) {
+        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);
+    }
+  }
+  for (DWARFDie Child = Die.getFirstChild(); Child; Child = Child.getSibling())
+    updateAddressDieMap(Child);
+}
+
 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;
-    }
-  }
-  return DWARFDie();
+  if (AddrDieMap.empty())
+    for (const DWARFDebugInfoEntry &D : DieArray)
+      if (D.getDepth() == 0)
+        updateAddressDieMap(DWARFDie(this, &D));
+  auto R = AddrDieMap.upper_bound(Address);
+  return R == AddrDieMap.begin() ? DWARFDie() : (--R)->second.second;
 }
 
 void
 DWARFUnit::getInlinedChainForAddress(uint64_t Address,
                                      SmallVectorImpl<DWARFDie> &InlinedChain) {
   // First, find a subprogram that contains the given address (the root
   // of inlined chain).
   DWARFDie SubprogramDIE;
   // Try to look for subprogram DIEs in the DWO file.
   parseDWO();
   if (DWO)
     SubprogramDIE = DWO->getUnit()->getSubprogramForAddress(Address);
   else
     SubprogramDIE = getSubprogramForAddress(Address);
 
   // Get inlined chain rooted at this subprogram DIE.
-  if (SubprogramDIE)
-    SubprogramDIE.getInlinedChainForAddress(Address, InlinedChain);
-  else
+  if (SubprogramDIE) {
+    while (SubprogramDIE) {
+      if (SubprogramDIE.isSubroutineDIE())
+        InlinedChain.push_back(SubprogramDIE);
+      SubprogramDIE = SubprogramDIE.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();