This is an archive of the discontinued LLVM Phabricator instance.

Add the ability for DWARFDie objects to get the parent DWARFDie.
ClosedPublic

Authored by clayborg on Dec 20 2016, 11:39 AM.

Details

Summary

In order for the llvm DWARF parser to be used in LLDB we will need to be able to get the parent of a DIE. This patch adds that functionality by changing the DWARFDebugInfoEntry class to store a depth field instead of a sibling index. Using a depth field allows us to easily calculate the sibling and the parent without increasing the size of DWARFDebugInfoEntry.

I tested llvm-dsymutil on a debug version of clang where this fully parses DWARF in over 1200 .o files to verify there was no serious regression in performance.

Added a full suite of unit tests to test this functionality.

Diff Detail

Event Timeline

clayborg updated this revision to Diff 82127.Dec 20 2016, 11:39 AM
clayborg retitled this revision from to Add the ability for DWARFDie objects to get the parent DWARFDie..
clayborg updated this object.
dblaikie added inline comments.Dec 20 2016, 12:49 PM
lib/DebugInfo/DWARF/DWARFUnit.cpp
412–416

Could this accidentally walk into children of another DIE?

(eg: if this is the last child of a DIE - then the next DIE at the same level could be not a sibling, but a child of the following DIE?)

A
  A1
B
  B1

The next DIE at the same level as A1 is B1 (unless the 'null' at the end of A's child list qualifies as the next sibling? But then, if the null is a DIE, what about its next sibling?)

If I read the test case correctly, it's testing CU{int, subprogram{param(i), param(j)}} - so it doesn't test this case where there's a following child at the same level that isn't a sibling. So if it does work, might be good to have a test case for it.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp
993–1004

I'd actually be inclined to make /less/ realistic DWARF, just to make it obvious that the semantics of DWARF aren't important here. We're just interested in tags and their children (probably don't have attributes at all - use the same tag for everything (perhaps some 'unknown' tag value, if possible)).

1072–1112

I don't think we need to test all these variations - the code seems pretty agnostic/independent of these features, such that the variations don't add a lot of value to the test coverage.

I will update the test cases to not add attributes and not do all the variants. David: let me know if you agree with my assessment on the A1 sibling case.

lib/DebugInfo/DWARF/DWARFUnit.cpp
416

Actually it won't because your example actually looks like:

A
  A1
  NULL
B
  B1
  NULL
NULL

So the sibling of "A1" would be the first NULL and that NULL wouldn't return a sibling (see line 409).

I can modify the test case to test this though as a follow on patch I was going to do was to actually not store the NULL dies in the DieArray. The NULL dies take up a lot of memory, but if I remove them, then I will need to make sure the above function behaves correctly by watching for a depth to go lower than the current depth, so adding a test as you mentioned is a good idea.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp
1004

Yeah, I can remove them. I was thinking about that as I was making the test.

1112

Sounds good, I will just do a single variation for this then.

clayborg updated this revision to Diff 82149.Dec 20 2016, 1:55 PM

Improved the tests to make sure we have coverage for:

CU
  A
    A1
    A2
  B
    B1
    B2
clayborg marked 2 inline comments as done.Dec 20 2016, 1:55 PM

Marked things as done.

dblaikie added inline comments.Dec 20 2016, 2:02 PM
unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp
985–999

Again, I'd probably skip tags (or is there something in the DWARF parser that has trouble dealing with a CU with no attributes?) & use the same tag repeatedly (preferably a clearly bogus tag - if we have a DW_TAG_unknown or something, that'd be ideal) to make it clear that the semantics of tag relationships aren't what's being tested here.

1006

The rest of this function appears to do too much testing - I doubt every relationship between every node in this tree pulls its weight in testing. Looks like they mostly test the same codepaths over and over again.

Could this be a bit more targeted? (test representative cases of interesting relationships - rather than every relationship)

clayborg updated this revision to Diff 82166.Dec 20 2016, 3:12 PM

Simplify DWARF test for testing relations to not use real tags.

dblaikie added inline comments.Dec 20 2016, 3:20 PM
unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp
984–992

Is there a need for nodes in this tree to be identifiable by their tags? Could they just be identifiable by pointers or other handles? (eg: could the first test be something like... oh, right, this is roundtripping through DWARF bytes so it's not the same objects on both sides)

Does this test need to roundtrip through DWARF bytes? Could we build some DWARF data types and demonstrate that their parent/sibling walks work correctly after we build them, without having to use DWARF bytes at all? Or is the API not practical to represent in-memory directly without backing bytes?

More like that test at the end that creates DWARFDie and tests it directly, without going through any DWARF byte emission/parsing.

1046–1096

This testing still seems unnecessarily exhaustive - it'd be good to understand which things are being tested and why. Selectively testing interesting parts of the tree walk to ensure things work, without having lots of redundancy - this way tests are easier to maintain and clearer what they are and aren't testing.

1098–1103

This looks like it could/should be a separate test case/function - since it's not related to the rest of this function.

I am not sure I would want to trim much more. Let me know if you see things I can trim. I could remove the "C2" die, but that is about it. Let me know if you see other stuff that can be trimmed.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp
992

The blocks you build with (classes in llvm/CodeGen) are different from the blocks that are in the DWARF parser API (llvm/DebugInfo/DWARF) so it really isn't practical to try and just create DIE objects since that isn't what our parser is using. So the only way to currently use the API is to actually encode bytes so we can decode them and use the DWARF parsing API.

1096

I believe this is close to the bare bones as we can get it. We are testing two DIEs, B and C that have children and making sure all functions get the right children and siblings. I can cut out the whole C tree, but then that won't test asking B2 to get its sibling and making sure we don't return C1 as its sibling... What would you cut from this? I can cut the B2 and C2, bit would rather not, as I want two consecutive DIEs with no children as a test.

1103

I can remove it,

clayborg updated this revision to Diff 82246.Dec 21 2016, 10:32 AM

Removed C2 from relations test to minimize the coverage to just what is needed and added an operator == to DWARFDie.

clayborg updated this revision to Diff 82257.Dec 21 2016, 12:39 PM

Fixed:

  • DWARFUnit::getDIEAtIndex() to assert and not bounds check index
  • Don't use getDIEAtIndex() in DWARFUnit::getParent(DWARFDebugInfoEntry *) or DWARFUnit::getSibling(DWARFDebugInfoEntry *)
  • Don't test "C" in the DWARF tests as we already covered the functionality when testing "B" and "C" is just there to ensure B keeps working.
dblaikie accepted this revision.Dec 21 2016, 1:01 PM
dblaikie edited edge metadata.

Some remaining ways to simplify the test cases - perhaps Adrian can lend a hand in person. Otherwise I'm happy to go through it in more detail/write up some examples of what I have in mind.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp
1039–1042

Not sure if this is interesting to test - I assume we already have pretty good coverage on node tags.

1043–1046

& probably have pretty good coverage on the hasChildren flag too.

1048–1052

Unless these are interestingly different, I'd just test one.

1054

What's the purpose of A? To test a node without children? Perhaps you could use B1 for that instead? (& then probably rename B -> A and C -> B)

1061–1063

I'd probably skip these too - the tags are sort of interesting, but really it's about the structure we're creating. I don't think checking the tags really makes this test much more robust/provides substantially better coverage for the change being tested.

(which was what motivated my earlier/original suggestion to use some obvious (& pre-existing) tag for everything, to demonstrate that the tags aren't interesting to the test)

1065–1067

Test just one of these? "// Verify that a node without children has an invalid first child" or something like that.

1069–1071

I'd probably skip these - you already tested parental links on A.

1073–1078

Pull this out into a separate test function/case.

This revision is now accepted and ready to land.Dec 21 2016, 1:01 PM
This revision was automatically updated to reflect the committed changes.