DWARF: Use a more compact internal representation in the manual dwarf index

[labath]

Summary

Reduce the size of the manual index by storing the entries in a more
compact form. This introduces the CompressedRef class, which is similar
to the DIERef class, but it is more compact because it lacks the
unit_offset field (which is not necessary now, as the unit is uniquely
identified by the rest of the fields). The user_id_t representation
would have the same size, but I did not use that here because:

• it's more complicated to convert it to/from a DIERef
• it's more clunky to handle as it is just an integer

The new class is for internal use only. It is converted to a regular
DIERef before returning it to the outside world.

[labath]

I made this depend on the DIERef patch instead of the other way around because the cleaner separation between dwo identifiers and compile unit offsets implemented in that patch makes it easier to implement this. It would still be possible to implement it the other way around, but the logic would be more complex, and it would have to be redone anyway once the DIERef patch lands.

Another possibility would be to just remove the unit_offset field from the DIERef class, and have the manual index keep using DIERefs. Once we introduce the dwo identifier, the unit offset is strictly optional, as the unit is uniquely identified by the other coordinates.

[clayborg]

In D63491#1548238, @labath wrote:

I made this depend on the DIERef patch instead of the other way around because the cleaner separation between dwo identifiers and compile unit offsets implemented in that patch makes it easier to implement this. It would still be possible to implement it the other way around, but the logic would be more complex, and it would have to be redone anyway once the DIERef patch lands.

Another possibility would be to just remove the unit_offset field from the DIERef class, and have the manual index keep using DIERefs. Once we introduce the dwo identifier, the unit offset is strictly optional, as the unit is uniquely identified by the other coordinates.

Lets just fix the DIERef class and remove the unit_offset field? No need for yet another minimal DIE reference class.

[labath]

Ok, sounds good. In that case, I think I can squeeze that change into the previous patch in this series.

[clayborg]

In D63491#1548400, @labath wrote:

Ok, sounds good. In that case, I think I can squeeze that change into the previous patch in this series.

That will be great, thanks.

source/Plugins/SymbolFile/DWARF/NameToDIE.h

public:
   size_t FindAllEntriesForUnit(const DWARFUnit &unit,
                                DIEArray &info_array) const;
 
   void
   ForEach(std::function<bool(lldb_private::ConstString name,
                              const DIERef &die_ref)> const
               &callback) const;
 
-protected:
-  lldb_private::UniqueCStringMap<DIERef> m_map;
+private:
+  class CompressedRef {
+  public:
+    CompressedRef(const DIERef &ref)
+        : m_dwo_num(ref.dwo_num().getValueOr(invalid_dwo_num)),
+          m_section(ref.section()), m_die_offset(ref.die_offset()) {}
+
+    operator DIERef() const {
+      return DIERef(dwo_num(), section(), llvm::None, die_offset());
+    }
+
+    llvm::Optional<uint32_t> dwo_num() const {
+      if (m_dwo_num < invalid_dwo_num)
+        return m_dwo_num;
+      return llvm::None;
+    }
+
+    DIERef::Section section() const {
+      return static_cast<DIERef::Section>(m_section);
+    }
+
+    dw_offset_t die_offset() const { return m_die_offset; }
+
+  private:
+    static constexpr uint32_t invalid_dwo_num = 0x7fffffff;
+
+    unsigned m_dwo_num : 31;
+    unsigned m_section : 1;
+    dw_offset_t m_die_offset;
+  };
+  static_assert(sizeof(CompressedRef) == 8, "");
+
+  lldb_private::UniqueCStringMap<CompressedRef> m_map;
 };
 
 #endif // SymbolFileDWARF_NameToDIE_h_

source/Plugins/SymbolFile/DWARF/NameToDIE.cpp

 using namespace lldb_private;
 
 void NameToDIE::Finalize() {
   m_map.Sort();
   m_map.SizeToFit();
 }
 
 void NameToDIE::Insert(ConstString name, const DIERef &die_ref) {
-  assert(die_ref.unit_offset().hasValue());
   m_map.Append(name, die_ref);
 }
 
 size_t NameToDIE::Find(ConstString name, DIEArray &info_array) const {
-  return m_map.GetValues(name, info_array);
+  std::vector<CompressedRef> compressed;
+  size_t result = m_map.GetValues(name, compressed);
+  for (const CompressedRef &ref : compressed)
+    info_array.push_back(ref);
+  return result;
 }
 
 size_t NameToDIE::Find(const RegularExpression &regex,
                        DIEArray &info_array) const {
-  return m_map.GetValues(regex, info_array);
+  std::vector<CompressedRef> compressed;
+  size_t result = m_map.GetValues(regex, compressed);
+  for (const CompressedRef &ref : compressed)
+    info_array.push_back(ref);
+  return result;
 }
 
 size_t NameToDIE::FindAllEntriesForUnit(const DWARFUnit &unit,
                                         DIEArray &info_array) const {
   const size_t initial_size = info_array.size();
   const uint32_t size = m_map.GetSize();
   for (uint32_t i = 0; i < size; ++i) {
-    const DIERef &die_ref = m_map.GetValueAtIndexUnchecked(i);
-    if (unit.GetSymbolFileDWARF().GetDwoNum() == die_ref.dwo_num() &&
-        unit.GetDebugSection() == die_ref.section() &&
-        unit.GetOffset() == *die_ref.unit_offset())
-      info_array.push_back(die_ref);
+    const CompressedRef &ref = m_map.GetValueAtIndexUnchecked(i);
+    if (unit.GetSymbolFileDWARF().GetDwoNum() == ref.dwo_num() &&
+        unit.GetDebugSection() == ref.section() &&
+        unit.GetOffset() <= ref.die_offset() &&
+        ref.die_offset() < unit.GetNextUnitOffset())
+      info_array.push_back(ref);
   }
   return info_array.size() - initial_size;
 }
 
 void NameToDIE::Dump(Stream *s) {
   const uint32_t size = m_map.GetSize();
   for (uint32_t i = 0; i < size; ++i) {
-    s->Format("{0} \"{1}\"\n", m_map.GetValueAtIndexUnchecked(i),
+    s->Format("{0} \"{1}\"\n", DIERef(m_map.GetValueAtIndexUnchecked(i)),
               m_map.GetCStringAtIndexUnchecked(i));
   }
 }
 
 void NameToDIE::ForEach(
     std::function<bool(ConstString name, const DIERef &die_ref)> const
         &callback) const {
   const uint32_t size = m_map.GetSize();