[DebugInfo] Change DWARFDebugAbbrev initialization

[bulbazord]

Summary

I plan on adding better error handling to DWARFDebugAbbrev, but first I
want us to be able to better reason about a state of a DWARFDebugAbbrev.
I want us to be able to initialize a DWARFDebugAbbrev in its complete
state instead of creating it and then calling an extract method
manually. If its Data field is populated, then parsing is not complete.
If Data is std::nullopt, then parsing is done and this section is
"finalized" in some sense.

Additionally, I have removed the clear() method. This makes sense for other
classes like DWARFAbbreviationDeclaration where we may want to re-use an object
repeatedly to avoid repeated initializations and allocations, but for
DWARFDebugAbbrev we pretty much create one and stick with it.

[aprantl]

Always a fan of getting rid of Clear() methods.

[fdeazeve]

+1 for this! I was hoping to do something similar for the accelerator tables later too!

[dblaikie]

FWIW - I'd actually be inclined to consider going in the opposite direction, to parsing the abbrevs even more lazily... I'd been looking into the performance of llvm-symbolizer without .debug_aranges (only CU ranges) and abbrev parsing ends up taking a not insignificant chunk of the time - not a deal breaker, but a bit of work that could be avoided if we lazily read abbrevs (in most cases we'd only need to read the first apprev - likely where the CU abbrev description is)

I'd prototyped a really hacked up patch that might give the general idea: https://pastebin.com/md943qvf

[bulbazord]

In D152947#4423100, @dblaikie wrote:

FWIW - I'd actually be inclined to consider going in the opposite direction, to parsing the abbrevs even more lazily... I'd been looking into the performance of llvm-symbolizer without .debug_aranges (only CU ranges) and abbrev parsing ends up taking a not insignificant chunk of the time - not a deal breaker, but a bit of work that could be avoided if we lazily read abbrevs (in most cases we'd only need to read the first apprev - likely where the CU abbrev description is)

I'd prototyped a really hacked up patch that might give the general idea: https://pastebin.com/md943qvf

I'm also interested in improving the time it takes to parse the abbrev section, I've seen it take up a non-trivial amount of time when parsing debug info in lldb.

One thing I've been working on for the last month or two is replacing portions of lldb's dwarf parsing logic with llvm's so that we can have one implementation. The process is non-trivial because there are a few differences between their logic. One thing that lldb's parser does really well is error handling, so I've been sinking a lot of that error handling into llvm's implementation. So far I've been able to remove lldb's DWARFAbbreviationDeclaration and DWARFAbbreviationDeclarationSet classes. I hope to be able to do the same for DWARFDebugAbbrev.

Quickly looking over your patch, I don't think that our goals are necessarily opposed. I think it's possible to be lazy and go fast while handling errors. There are 2 things I think need to happen before I can remove lldb's implementation of DWARFDebugAbbrev:

1. DWARFDebugAbbrev needs to meaningfully surface errors. Right now it does 0 error handling at all, so there's no insight into what failed or why when an error occurs. This was true for the other 2 classes a few months ago, now they are better. I want to eventually have parse and getAbbreviationDeclarationSet return llvm::Error and llvm::Expected respectively.
2. DWARFDebugAbbrev::begin() needs to stop calling parse. There's no way to meaningfully surface an error from begin. I want to instead force all users to call parse explicitly and handle an error before being able to iterate over all the DeclSets. If you want just one specific DeclSet, you wouldn't have to pay the cost of parsing everything, just the cost of error handling from that one extraction. This patch is the first step towards doing that, specifically I want Data to always be not std::nullopt while there is still information to parse. I'm open to different approaches here though.

What do you think about this? I'm happy to chat further.

[dblaikie]

In D152947#4423192, @bulbazord wrote:

In D152947#4423100, @dblaikie wrote:

FWIW - I'd actually be inclined to consider going in the opposite direction, to parsing the abbrevs even more lazily... I'd been looking into the performance of llvm-symbolizer without .debug_aranges (only CU ranges) and abbrev parsing ends up taking a not insignificant chunk of the time - not a deal breaker, but a bit of work that could be avoided if we lazily read abbrevs (in most cases we'd only need to read the first apprev - likely where the CU abbrev description is)

I'd prototyped a really hacked up patch that might give the general idea: https://pastebin.com/md943qvf

I'm also interested in improving the time it takes to parse the abbrev section, I've seen it take up a non-trivial amount of time when parsing debug info in lldb.

One thing I've been working on for the last month or two is replacing portions of lldb's dwarf parsing logic with llvm's so that we can have one implementation. The process is non-trivial because there are a few differences between their logic. One thing that lldb's parser does really well is error handling, so I've been sinking a lot of that error handling into llvm's implementation. So far I've been able to remove lldb's DWARFAbbreviationDeclaration and DWARFAbbreviationDeclarationSet classes. I hope to be able to do the same for DWARFDebugAbbrev.

Quickly looking over your patch, I don't think that our goals are necessarily opposed. I think it's possible to be lazy and go fast while handling errors. There are 2 things I think need to happen before I can remove lldb's implementation of DWARFDebugAbbrev:

1. DWARFDebugAbbrev needs to meaningfully surface errors. Right now it does 0 error handling at all, so there's no insight into what failed or why when an error occurs. This was true for the other 2 classes a few months ago, now they are better. I want to eventually have parse and getAbbreviationDeclarationSet return llvm::Error and llvm::Expected respectively.
2. DWARFDebugAbbrev::begin() needs to stop calling parse. There's no way to meaningfully surface an error from begin. I want to instead force all users to call parse explicitly and handle an error before being able to iterate over all the DeclSets.

I was trying to avoid parsing more than one /element/ of a DeclSet (assuming a DeclSet is all the abbreviations for one CU ~roughly) - to symbolize you basically 'need' to parse all the CU DIEs to collect all the ranges so you can do a quick search over ranges - which means if you have to parse whole DeclSets then the symbolizer won't be able to improve here (it's not critical, by any means - I think the symbolizer's still fast enough, but I was hoping to bring it up in case it resonated with you/anyone, if only to keep it in mind as a future possibility, even if not solving it right now).

[bulbazord]

In D152947#4425942, @dblaikie wrote:

In D152947#4423192, @bulbazord wrote:

In D152947#4423100, @dblaikie wrote:

FWIW - I'd actually be inclined to consider going in the opposite direction, to parsing the abbrevs even more lazily... I'd been looking into the performance of llvm-symbolizer without .debug_aranges (only CU ranges) and abbrev parsing ends up taking a not insignificant chunk of the time - not a deal breaker, but a bit of work that could be avoided if we lazily read abbrevs (in most cases we'd only need to read the first apprev - likely where the CU abbrev description is)

I'd prototyped a really hacked up patch that might give the general idea: https://pastebin.com/md943qvf

I'm also interested in improving the time it takes to parse the abbrev section, I've seen it take up a non-trivial amount of time when parsing debug info in lldb.

One thing I've been working on for the last month or two is replacing portions of lldb's dwarf parsing logic with llvm's so that we can have one implementation. The process is non-trivial because there are a few differences between their logic. One thing that lldb's parser does really well is error handling, so I've been sinking a lot of that error handling into llvm's implementation. So far I've been able to remove lldb's DWARFAbbreviationDeclaration and DWARFAbbreviationDeclarationSet classes. I hope to be able to do the same for DWARFDebugAbbrev.

Quickly looking over your patch, I don't think that our goals are necessarily opposed. I think it's possible to be lazy and go fast while handling errors. There are 2 things I think need to happen before I can remove lldb's implementation of DWARFDebugAbbrev:

1. DWARFDebugAbbrev needs to meaningfully surface errors. Right now it does 0 error handling at all, so there's no insight into what failed or why when an error occurs. This was true for the other 2 classes a few months ago, now they are better. I want to eventually have parse and getAbbreviationDeclarationSet return llvm::Error and llvm::Expected respectively.
2. DWARFDebugAbbrev::begin() needs to stop calling parse. There's no way to meaningfully surface an error from begin. I want to instead force all users to call parse explicitly and handle an error before being able to iterate over all the DeclSets.

I was trying to avoid parsing more than one /element/ of a DeclSet (assuming a DeclSet is all the abbreviations for one CU ~roughly) - to symbolize you basically 'need' to parse all the CU DIEs to collect all the ranges so you can do a quick search over ranges - which means if you have to parse whole DeclSets then the symbolizer won't be able to improve here (it's not critical, by any means - I think the symbolizer's still fast enough, but I was hoping to bring it up in case it resonated with you/anyone, if only to keep it in mind as a future possibility, even if not solving it right now).

It definitely resonates with me, my colleagues and I do care a lot about the performance of the DWARF parser in LLVM and I think we'd like to be able to only do the necessary work in parsing. I don't think anything about the design I'm working towards will prevent us from being able to add "lazy" functionality, though we might have to think about what methods we expose to support that functionality.

[dblaikie]

I was trying to avoid parsing more than one /element/ of a DeclSet (assuming a DeclSet is all the abbreviations for one CU ~roughly) - to symbolize you basically 'need' to parse all the CU DIEs to collect all the ranges so you can do a quick search over ranges - which means if you have to parse whole DeclSets then the symbolizer won't be able to improve here (it's not critical, by any means - I think the symbolizer's still fast enough, but I was hoping to bring it up in case it resonated with you/anyone, if only to keep it in mind as a future possibility, even if not solving it right now).

It definitely resonates with me, my colleagues and I do care a lot about the performance of the DWARF parser in LLVM and I think we'd like to be able to only do the necessary work in parsing. I don't think anything about the design I'm working towards will prevent us from being able to add "lazy" functionality, though we might have to think about what methods we expose to support that functionality.

Yeah, I don't know that it'd prevent/make it especially harder, but maybe there's ways to steer more towards that lazy direction - it seems like this change is cementing a little more the idea of up-front parsing, where maybe it's worth considering going further away from that.

[bulbazord]

In D152947#4429019, @dblaikie wrote:

I was trying to avoid parsing more than one /element/ of a DeclSet (assuming a DeclSet is all the abbreviations for one CU ~roughly) - to symbolize you basically 'need' to parse all the CU DIEs to collect all the ranges so you can do a quick search over ranges - which means if you have to parse whole DeclSets then the symbolizer won't be able to improve here (it's not critical, by any means - I think the symbolizer's still fast enough, but I was hoping to bring it up in case it resonated with you/anyone, if only to keep it in mind as a future possibility, even if not solving it right now).

It definitely resonates with me, my colleagues and I do care a lot about the performance of the DWARF parser in LLVM and I think we'd like to be able to only do the necessary work in parsing. I don't think anything about the design I'm working towards will prevent us from being able to add "lazy" functionality, though we might have to think about what methods we expose to support that functionality.

Yeah, I don't know that it'd prevent/make it especially harder, but maybe there's ways to steer more towards that lazy direction - it seems like this change is cementing a little more the idea of up-front parsing, where maybe it's worth considering going further away from that.

This change in particular enforces the idea that if you create a DWARFDebugAbbrev object, you should supply a DataExtractor instead of creating one and supplying one later via the extract method. You don't have to actually parse anything upon instantiation. The next step I was going to do here is to remove the call to parse() in the begin() method and add an assertion that enforces users call parse() before iterating over a DWARFDebugAbbrev object. If you want to iterate over one, presumably you wanted to actually parse the whole thing (at least that's what the current behavior is. We could expose a lazy version of the iterator that doesn't enforce this though). There is still DWARFDebugAbbrev::getAbbreviationDeclarationSet which will get you just one set without parsing the entire section (and will not have the same assertion so that we can be lazy). Further up you said you wanted to avoid parsing more than just one Decl in a DeclSet, and I would assume that is the function that you would want to make "lazy" -- Presumably you know what the CUAbbrOffset would be from the CU header (or the index in the DWP case). It would be a matter of adding a lazy variant of this method which only parses the AbbreviationDeclarations that you ask it to (but still does error checking as needed). If it makes sense to be completely lazy, we can remove the support for being eager entirely. I just want us to be able to go fast and to handle errors instead of dropping malformed DWARF on the floor.

This is roughly how I imagined it working (which is why I feel our goals are not opposed). What do you think?

[dblaikie]

In D152947#4429072, @bulbazord wrote:

In D152947#4429019, @dblaikie wrote:

I was trying to avoid parsing more than one /element/ of a DeclSet (assuming a DeclSet is all the abbreviations for one CU ~roughly) - to symbolize you basically 'need' to parse all the CU DIEs to collect all the ranges so you can do a quick search over ranges - which means if you have to parse whole DeclSets then the symbolizer won't be able to improve here (it's not critical, by any means - I think the symbolizer's still fast enough, but I was hoping to bring it up in case it resonated with you/anyone, if only to keep it in mind as a future possibility, even if not solving it right now).

It definitely resonates with me, my colleagues and I do care a lot about the performance of the DWARF parser in LLVM and I think we'd like to be able to only do the necessary work in parsing. I don't think anything about the design I'm working towards will prevent us from being able to add "lazy" functionality, though we might have to think about what methods we expose to support that functionality.

Yeah, I don't know that it'd prevent/make it especially harder, but maybe there's ways to steer more towards that lazy direction - it seems like this change is cementing a little more the idea of up-front parsing, where maybe it's worth considering going further away from that.

This change in particular enforces the idea that if you create a DWARFDebugAbbrev object, you should supply a DataExtractor instead of creating one and supplying one later via the extract method. You don't have to actually parse anything upon instantiation.

Yeah, that bit I can't argue with/seems fine enough - but the direction beyond that's perhaps where I'm expressing some concern.

The next step I was going to do here is to remove the call to parse() in the begin() method and add an assertion that enforces users call parse() before iterating over a DWARFDebugAbbrev object.

Yeah, I guess that's the bit where I'm not so sure/seems like it's cementing the "parse up front" idea a bit more formally, when instead we could be going in the other direction.

If you want to iterate over one, presumably you wanted to actually parse the whole thing (at least that's what the current behavior is. We could expose a lazy version of the iterator that doesn't enforce this though).

Not necessarily - using lazy fallible iterators might be suitable: https://llvm.org/docs/ProgrammersManual.html#building-fallible-iterators-and-iterator-ranges - maybe someone's searching through the list until they find something of interest and then want to stop. That, I think, is the direction @lhames
was going in - that whatever you did, you only got as much as you needed/didn't parse more - because maybe something later is corrupted (or just inefficient to parse) but it shouldn't stop you from seeing something earlier in a dumping tool, for instance.

There is still DWARFDebugAbbrev::getAbbreviationDeclarationSet which will get you just one set without parsing the entire section (and will not have the same assertion so that we can be lazy). Further up you said you wanted to avoid parsing more than just one Decl in a DeclSet, and I would assume that is the function that you would want to make "lazy" -- Presumably you know what the CUAbbrOffset would be from the CU header (or the index in the DWP case). It would be a matter of adding a lazy variant of this method which only parses the AbbreviationDeclarations that you ask it to (but still does error checking as needed). If it makes sense to be completely lazy, we can remove the support for being eager entirely. I just want us to be able to go fast and to handle errors instead of dropping malformed DWARF on the floor.

This is roughly how I imagined it working (which is why I feel our goals are not opposed). What do you think?

Yeah, I don't think it gets too much in the way - as you say, can still get one specific set, and can still add laziness there. Though maybe it's worth considering lazy iteration, not for my particular need/situation, but in general - for llvm-dwarfdump to be able to dump as much as it can, rather than failing on the last abbrev set and then not dumping the previous ones, for instance.

llvm/lib/DebugInfo/DWARF/DWARFContext.cpp

941

950

[bulbazord]

In D152947#4429207, @dblaikie wrote:

If you want to iterate over one, presumably you wanted to actually parse the whole thing (at least that's what the current behavior is. We could expose a lazy version of the iterator that doesn't enforce this though).

Not necessarily - using lazy fallible iterators might be suitable: https://llvm.org/docs/ProgrammersManual.html#building-fallible-iterators-and-iterator-ranges - maybe someone's searching through the list until they find something of interest and then want to stop. That, I think, is the direction @lhames
was going in - that whatever you did, you only got as much as you needed/didn't parse more - because maybe something later is corrupted (or just inefficient to parse) but it shouldn't stop you from seeing something earlier in a dumping tool, for instance.

There is still DWARFDebugAbbrev::getAbbreviationDeclarationSet which will get you just one set without parsing the entire section (and will not have the same assertion so that we can be lazy). Further up you said you wanted to avoid parsing more than just one Decl in a DeclSet, and I would assume that is the function that you would want to make "lazy" -- Presumably you know what the CUAbbrOffset would be from the CU header (or the index in the DWP case). It would be a matter of adding a lazy variant of this method which only parses the AbbreviationDeclarations that you ask it to (but still does error checking as needed). If it makes sense to be completely lazy, we can remove the support for being eager entirely. I just want us to be able to go fast and to handle errors instead of dropping malformed DWARF on the floor.

This is roughly how I imagined it working (which is why I feel our goals are not opposed). What do you think?

Yeah, I don't think it gets too much in the way - as you say, can still get one specific set, and can still add laziness there. Though maybe it's worth considering lazy iteration, not for my particular need/situation, but in general - for llvm-dwarfdump to be able to dump as much as it can, rather than failing on the last abbrev set and then not dumping the previous ones, for instance.

I'll take a look at the fallible iterator link you gave me and see what it would look like to implement that. I don't mind doing that if it makes the most sense in terms of usability/performance. Thanks for sharing that!

[bulbazord]

llvm/lib/DebugInfo/DWARF/DWARFContext.cpp

941

fecabf40069231808f6ce507f9048abcbb015f1f

[fdeazeve]

using lazy fallible iterators might be suitable:

@bulbazord, if you end up using these, let's chat as I'd love to understand them better. To name a couple of things that puzzled me, it exposes these methods:

/// Construct a fallible iterator that *cannot* be used as an end-of-range
/// value.
static fallible_iterator itr(Underlying I, Error &Err) {

/// Construct a fallible iterator that can be used as an end-of-range value.
/// A value created by this method can be dereferenced (if the underlying
/// value points at a valid value)
static fallible_iterator end(Underlying I) {

Not being able to construct a "begin" that is also "end" seems counter-intuitive (iterators often test emptiness through begin==end). Similarly, constructing an "end" that can be dereferenced is not usual? In the process of asking these questions, I think I now know the answer, but I don't want to bias your investigation ;)

[dblaikie]

In D152947#4430336, @fdeazeve wrote:

using lazy fallible iterators might be suitable:

@bulbazord, if you end up using these, let's chat as I'd love to understand them better. To name a couple of things that puzzled me, it exposes these methods:

/// Construct a fallible iterator that *cannot* be used as an end-of-range
/// value.
static fallible_iterator itr(Underlying I, Error &Err) {

/// Construct a fallible iterator that can be used as an end-of-range value.
/// A value created by this method can be dereferenced (if the underlying
/// value points at a valid value)
static fallible_iterator end(Underlying I) {

Not being able to construct a "begin" that is also "end" seems counter-intuitive (iterators often test emptiness through begin==end). Similarly, constructing an "end" that can be dereferenced is not usual? In the process of asking these questions, I think I now know the answer, but I don't want to bias your investigation ;)

I think the idea here is an attempt to generalize, perhaps overly so - to cover cases where you might expose iterators to subranges (and the consumer might know it's a subrange, so it's an "end" iterator in that it's the end of a subrange, but not necessarily an invalid iterator) - I think the words are all a bit more complicated/generalizing than may be necessary. The point is that the iterator you might increment forward is the one you get from the function that also takes an Error out parameter, and the other iterator that doesn't have such a parameter is the one you compare the former to.

llvm/include/llvm/DebugInfo/DWARF/DWARFDebugAbbrev.h

class DWARFDebugAbbrev {
   using DWARFAbbreviationDeclarationSetMap =
       std::map<uint64_t, DWARFAbbreviationDeclarationSet>;
 
   mutable DWARFAbbreviationDeclarationSetMap AbbrDeclSets;
   mutable DWARFAbbreviationDeclarationSetMap::const_iterator PrevAbbrOffsetPos;
   mutable std::optional<DataExtractor> Data;
 
 public:
-  DWARFDebugAbbrev();
+  DWARFDebugAbbrev(DataExtractor Data);
 
   const DWARFAbbreviationDeclarationSet *
   getAbbreviationDeclarationSet(uint64_t CUAbbrOffset) const;
 
   void dump(raw_ostream &OS) const;
   void parse() const;
-  void extract(DataExtractor Data);
 
   DWARFAbbreviationDeclarationSetMap::const_iterator begin() const {
     parse();
     return AbbrDeclSets.begin();
   }
 
   DWARFAbbreviationDeclarationSetMap::const_iterator end() const {
     return AbbrDeclSets.end();
   }
-
-private:
-  void clear();
 };
 
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_DWARF_DWARFDEBUGABBREV_H

llvm/lib/DebugInfo/DWARF/DWARFContext.cpp

DWARFGdbIndex &DWARFContext::getGdbIndex() {
   return *GdbIndex;
 }
 
 const DWARFDebugAbbrev *DWARFContext::getDebugAbbrev() {
   if (Abbrev)
     return Abbrev.get();
 
   DataExtractor abbrData(DObj->getAbbrevSection(), isLittleEndian(), 0);
-
-  Abbrev.reset(new DWARFDebugAbbrev());
-  Abbrev->extract(abbrData);
+  Abbrev.reset(new DWARFDebugAbbrev(abbrData));
   return Abbrev.get();
 }
 
 const DWARFDebugAbbrev *DWARFContext::getDebugAbbrevDWO() {
   if (AbbrevDWO)
     return AbbrevDWO.get();
 
   DataExtractor abbrData(DObj->getAbbrevDWOSection(), isLittleEndian(), 0);
-  AbbrevDWO.reset(new DWARFDebugAbbrev());
-  AbbrevDWO->extract(abbrData);
+  AbbrevDWO.reset(new DWARFDebugAbbrev(abbrData));
   return AbbrevDWO.get();
 }
 
 const DWARFDebugLoc *DWARFContext::getDebugLoc() {
   if (Loc)
     return Loc.get();
 
   // Assume all units have the same address byte size.

llvm/lib/DebugInfo/DWARF/DWARFDebugAbbrev.cpp

if (RangeStart != RangeEnd)
       Stream << "-" << RangeEnd;
     // If there is at least one more range, add a separator.
     if (Current != End)
       Stream << ", ";
   }
   return Buffer;
 }
 
-DWARFDebugAbbrev::DWARFDebugAbbrev() { clear(); }
-
-void DWARFDebugAbbrev::clear() {
-  AbbrDeclSets.clear();
-  PrevAbbrOffsetPos = AbbrDeclSets.end();
-}
-
-void DWARFDebugAbbrev::extract(DataExtractor Data) {
-  clear();
-  this->Data = Data;
-}
+DWARFDebugAbbrev::DWARFDebugAbbrev(DataExtractor Data)
+    : AbbrDeclSets(), PrevAbbrOffsetPos(AbbrDeclSets.end()), Data(Data) {}
 
 void DWARFDebugAbbrev::parse() const {
   if (!Data)
     return;
   uint64_t Offset = 0;
   auto I = AbbrDeclSets.begin();
   while (Data->isValidOffset(Offset)) {
     while (I != AbbrDeclSets.end() && I->first < Offset)