DWZ 04/06: ManualDWARFIndex::GetGlobalVariables for DIEs in PUs

[jankratochvil]

Summary

Rarely (GlobalVariablesTestCase-test_c_global_variables) a DIE can be only in PU (PartialUnit), that is if a DIE is a static constant variable (g_file_static_int) so that it has no location address.

Patch has been optimized for minimal code added despite the performance is suboptimal for DWZ files. It also should not affect non-DWZ files performance.

All DWZ patches are also applied in: git clone -b dwz git://git.jankratochvil.net/lldb

[jankratochvil]

Replaced by D96240.

source/Plugins/SymbolFile/DWARF/ManualDWARFIndex.h

 //===-- ManulaDWARFIndex.h -------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLDB_MANUALDWARFINDEX_H
 #define LLDB_MANUALDWARFINDEX_H
 
 #include "Plugins/SymbolFile/DWARF/DWARFIndex.h"
+#include "Plugins/SymbolFile/DWARF/DWARFUnit.h"
 #include "Plugins/SymbolFile/DWARF/NameToDIE.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/Support/RWMutex.h"
+
+#include <unordered_map>
 
 namespace lldb_private {
 class ManualDWARFIndex : public DWARFIndex {
 public:
   ManualDWARFIndex(Module &module, DWARFDebugInfo *debug_info,
                    llvm::DenseSet<dw_offset_t> units_to_avoid = {})
       : DWARFIndex(module), m_debug_info(debug_info),
         m_units_to_avoid(std::move(units_to_avoid)) {}
 
+  ~ManualDWARFIndex() override;
+
   void Preload() override { Index(); }
 
   void GetGlobalVariables(ConstString basename, DIEArray &offsets) override;
   void GetGlobalVariables(const RegularExpression &regex,
                           DIEArray &offsets) override;
   void GetGlobalVariables(const DWARFUnit &cu, DIEArray &offsets) override;
   void GetObjCMethods(ConstString class_name, DIEArray &offsets) override;
   void GetCompleteObjCClass(ConstString class_name, bool must_be_implementation,
IndexUnitImpl(DWARFUnit &unit, const lldb::LanguageType cu_language,
                 const DWARFFormValue::FixedFormSizes &fixed_form_sizes,
                 const dw_offset_t cu_offset, IndexSet &set);
 
   /// Non-null value means we haven't built the index yet.
   DWARFDebugInfo *m_debug_info;
   /// Which dwarf units should we skip while building the index.
   llvm::DenseSet<dw_offset_t> m_units_to_avoid;
 
+  void AddExtractedPU(DWARFUnit &importer, DWARFUnit &importee);
+
   IndexSet m_set;
+
+  // All DW_TAG_partial_unit's extracted for Index-ing this DW_TAG_compile_unit.
+  struct ExtractedForUnit {
+    // FIXME: The pointer is already contained in the value; but we wound need
+    // a combination of DenseSet::insert_as and DenseSet::try_emplace.
+    std::unordered_map<const DWARFUnit *, DWARFUnit::ScopedExtractDIEs> m_map;
+    llvm::sys::RWMutex m_mutex;
+  };
+  std::unordered_map<const DWARFUnit *, ExtractedForUnit> m_extracted_pu;
+  llvm::sys::RWMutex m_extracted_pu_mutex;
 };
 } // namespace lldb_private
 
 #endif // LLDB_MANUALDWARFINDEX_H

source/Plugins/SymbolFile/DWARF/ManualDWARFIndex.cpp

case DW_TAG_imported_unit:
                   "CU 0x%8.8" PRIx32 " DIE 0x%8.8" PRIx32
                   " DW_TAG_imported_unit of DIE 0x%16.16" PRIx32
                   " is not the target CU first DIE 0x%8.8" PRIx32,
                   unit.GetOffset(), die.GetOffset(),
                   import_offset, import_cu_firstdie_offset);
           break;
         }
         import_cu->SetMainCU(&main_unit);
+        AddExtractedPU(unit, *import_cu);
         IndexUnit(*import_cu,set);
       }
       break;
 
     default:
       continue;
     }
   }
 }
 
 void ManualDWARFIndex::GetGlobalVariables(ConstString basename, DIEArray &offsets) {
   Index();
   m_set.globals.Find(basename, offsets);
 }
 
 void ManualDWARFIndex::GetGlobalVariables(const RegularExpression &regex,
                                           DIEArray &offsets) {
   Index();
   m_set.globals.Find(regex, offsets);
 }
 
 void ManualDWARFIndex::GetGlobalVariables(const DWARFUnit &cu,
                                           DIEArray &offsets) {
   Index();
+  if (m_extracted_pu.empty()) {
     m_set.globals.FindAllEntriesForCompileUnit(cu.GetOffset(), offsets);
+    return;
+  }
+  // FIXME: It would be more memory and CPU effective to pack it as compact
+  // read-only data structure at the end of indexing.
+  std::unordered_set<const DWARFUnit *> todo;
+  std::unordered_set<dw_offset_t> found;
+  todo.insert(&cu);
+  while (!todo.empty()) {
+    const DWARFUnit *work = *todo.cbegin();
+    todo.erase(todo.cbegin());
+    if (!found.insert(work->GetOffset()).second) {
+      m_module.GetObjectFile()->GetModule()->ReportError(
+         "CU 0x%8.8" PRIx32 " leads to duplicate DW_TAG_imported_unit "
+         "for PU 0x%8.8" PRIx32,
+         cu.GetOffset(), work->GetOffset());
+      continue;
+    }
+    const auto it = m_extracted_pu.find(work);
+    if (it == m_extracted_pu.cend())
+      continue;
+    const ExtractedForUnit &for_unit = it->second;
+    for (const auto &pair : for_unit.m_map) {
+      const DWARFUnit *new_work = pair.first;
+      if (!todo.insert(new_work).second)
+        m_module.GetObjectFile()->GetModule()->ReportError(
+           "CU 0x%8.8" PRIx32 " leads to duplicate DW_TAG_imported_unit "
+           "from PU 0x%8.8" PRIx32 " to PU 0x%8.8" PRIx32,
+           cu.GetOffset(), work->GetOffset(), new_work->GetOffset());
+    }
+  }
+  m_set.globals.FindAllEntriesForCompileUnit(found, offsets);
 }
 
 void ManualDWARFIndex::GetObjCMethods(ConstString class_name,
                                       DIEArray &offsets) {
   Index();
   m_set.objc_class_selectors.Find(class_name, offsets);
 }
 
void ManualDWARFIndex::Dump(Stream &s) {
   m_set.objc_class_selectors.Dump(&s);
   s.Printf("\nGlobals and statics:\n");
   m_set.globals.Dump(&s);
   s.Printf("\nTypes:\n");
   m_set.types.Dump(&s);
   s.Printf("\nNamespaces:\n");
   m_set.namespaces.Dump(&s);
 }
+
+void ManualDWARFIndex::AddExtractedPU(
+    DWARFUnit &importer, DWARFUnit &importee) {
+  ExtractedForUnit *for_importer;
+  {
+    llvm::sys::ScopedWriter guard_all(m_extracted_pu_mutex);
+    for_importer = &m_extracted_pu[&importer];
+  }
+  llvm::sys::ScopedWriter guard_for_unit(for_importer->m_mutex);
+  // It may be already present as we do not clear m_map for ClearDIEsRWLocked()
+  // as it is required during its later use.
+  for_importer->m_map.emplace(&importee, &importee);
+}
+
+// We could try to call ClearDIEsRWLocked() on an already destroyed DWARFUnit.
+ManualDWARFIndex::~ManualDWARFIndex() {
+  for (auto &all_pair : m_extracted_pu) {
+    ExtractedForUnit &for_unit = all_pair.second;
+    for (auto &unit_pair : for_unit.m_map) {
+      DWARFUnit::ScopedExtractDIEs &scoped = unit_pair.second;
+      scoped.Disable();
+    }
+  }
+}

source/Plugins/SymbolFile/DWARF/NameToDIE.h

 //===-- NameToDIE.h ---------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SymbolFileDWARF_NameToDIE_h_
 #define SymbolFileDWARF_NameToDIE_h_
 
 #include <functional>
+#include <unordered_set>
 
 #include "DIERef.h"
 #include "lldb/Core/UniqueCStringMap.h"
 #include "lldb/Core/dwarf.h"
 #include "lldb/lldb-defines.h"
 
 class SymbolFileDWARF;
 
public:
   void Finalize();
 
   size_t Find(const lldb_private::ConstString &name,
               DIEArray &info_array) const;
 
   size_t Find(const lldb_private::RegularExpression &regex,
               DIEArray &info_array) const;
 
+  size_t FindAllEntriesForCompileUnit(
+      std::function<bool(dw_offset_t)> compare, DIEArray &info_array) const;
+
   size_t FindAllEntriesForCompileUnit(dw_offset_t cu_offset,
                                       DIEArray &info_array) const;
 
+  size_t FindAllEntriesForCompileUnit(
+      const std::unordered_set<dw_offset_t> &cu_offsets,
+      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;
 };
 
 #endif // SymbolFileDWARF_NameToDIE_h_

source/Plugins/SymbolFile/DWARF/NameToDIE.cpp

size_t NameToDIE::Find(const ConstString &name, DIEArray &info_array) const {
   return m_map.GetValues(name, info_array);
 }
 
 size_t NameToDIE::Find(const RegularExpression &regex,
                        DIEArray &info_array) const {
   return m_map.GetValues(regex, info_array);
 }
 
-size_t NameToDIE::FindAllEntriesForCompileUnit(dw_offset_t cu_offset,
-                                               DIEArray &info_array) const {
+size_t NameToDIE::FindAllEntriesForCompileUnit(
+    std::function<bool(dw_offset_t)> compare, 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 (cu_offset == die_ref.cu_offset)
+    if (compare(die_ref.cu_offset))
       info_array.push_back(die_ref);
   }
   return info_array.size() - initial_size;
 }
 
+size_t NameToDIE::FindAllEntriesForCompileUnit(dw_offset_t cu_offset,
+                                               DIEArray &info_array) const {
+  return FindAllEntriesForCompileUnit([cu_offset](dw_offset_t offset) {
+    return offset == cu_offset;
+  }, info_array);
+}
+
+size_t NameToDIE::FindAllEntriesForCompileUnit(
+    const std::unordered_set<dw_offset_t> &cu_offsets,
+    DIEArray &info_array) const {
+  return FindAllEntriesForCompileUnit([&cu_offsets](dw_offset_t offset) {
+    return cu_offsets.count(offset) != 0;
+  }, info_array);
+}
+
 void NameToDIE::Dump(Stream *s) {
   const uint32_t size = m_map.GetSize();
   for (uint32_t i = 0; i < size; ++i) {
     ConstString cstr = m_map.GetCStringAtIndex(i);
     const DIERef &die_ref = m_map.GetValueAtIndexUnchecked(i);
     s->Printf("%p: {0x%8.8x/0x%8.8x} \"%s\"\n", (const void *)cstr.GetCString(),
               die_ref.cu_offset, die_ref.die_offset, cstr.GetCString());
   }