This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by danielcdh on Apr 18 2017, 10:02 AM.

Details

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.

Event Timeline

danielcdh created this revision.Apr 18 2017, 10:02 AM
dblaikie added inline comments.Apr 18 2017, 10:18 AM
include/llvm/DebugInfo/DWARF/DWARFUnit.h
140

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

danielcdh added inline comments.Apr 18 2017, 10:34 AM
include/llvm/DebugInfo/DWARF/DWARFUnit.h
140

They did not provide upper_bound method.

danielcdh updated this revision to Diff 95610.Apr 18 2017, 12:43 PM

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 accepted this revision.Apr 18 2017, 1:20 PM
dblaikie added inline comments.
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)?

This revision is now accepted and ready to land.Apr 18 2017, 1:20 PM
danielcdh updated this revision to Diff 95622.Apr 18 2017, 2:02 PM
danielcdh marked 3 inline comments as done.

update

danielcdh added inline comments.Apr 18 2017, 2:02 PM
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 updated this revision to Diff 95623.Apr 18 2017, 2:05 PM

update comment

"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 updated this revision to Diff 95635.Apr 18 2017, 2:32 PM

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.

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

danielcdh updated this revision to Diff 95653.Apr 18 2017, 4:02 PM

update the code to ignore 0-sized ranges.

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

Looks good - commit when ready :)

danielcdh closed this revision.Apr 19 2017, 8:03 AM
This revision is now accepted and ready to land.Apr 19 2017, 11:19 AM
danielcdh updated this revision to Diff 95786.Apr 19 2017, 11:20 AM

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

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 marked an inline comment as done.Apr 19 2017, 1:07 PM

Will have separate patch to address other concerns.

danielcdh closed this revision.Apr 19 2017, 1:22 PM
danielcdh marked an inline comment as done.Apr 19 2017, 2:05 PM

updated in NFC commit r300753.