DebugNamesDWARFIndex: Add support for partial indexes

[labath]

Summary

It possible that a single module has indexed and non-indexed compile
units. In this case, we can use the fast indexed lookup for the first
ones and fall back to the manual index for the others.

This patch implements this functionality by adding a units_to_avoid
argument to the ManualDWARFIndex constructor. Any units present in that
list will be ignored for the purposes of manual index. Individual
DebugNamesDWARFIndex then always consult both the manual fallback index
as well as the index in the .debug_names section.

[clayborg]

Just one nit you can choose to fix or not.

source/Plugins/SymbolFile/DWARF/ManualDWARFIndex.cpp

39–41 ↗

(On Diff #150155)

Simpler code:

if (!unit || m_units_to_avoid.count(unit->GetOffset())
  continue;

lldb/trunk/lit/SymbolFile/DWARF/dwarf5-partial-index.cpp

+// Test that we return complete results when only a part of the binary is built
+// with an index.
+
+// REQUIRES: lld
+
+// RUN: clang %s -g -c -emit-llvm -o - --target=x86_64-pc-linux -DONE | \
+// RUN:   llc -accel-tables=Dwarf -filetype=obj -o %t-1.o
+// RUN: clang %s -g -c -emit-llvm -o - --target=x86_64-pc-linux -DTWO | \
+// RUN:   llc -accel-tables=Disable -filetype=obj -o %t-2.o
+// RUN: ld.lld %t-1.o %t-2.o -o %t
+// RUN: lldb-test symbols --find=variable --name=foo  %t | FileCheck %s
+
+// CHECK: Found 2 variables:
+#ifdef ONE
+namespace one {
+int foo;
+// CHECK-DAG: name = "foo", {{.*}} decl = dwarf5-partial-index.cpp:[[@LINE-1]]
+} // namespace one
+extern "C" void _start() {}
+#else
+namespace two {
+int foo;
+// CHECK-DAG: name = "foo", {{.*}} decl = dwarf5-partial-index.cpp:[[@LINE-1]]
+} // namespace two
+#endif

lldb/trunk/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h

 //===-- DebugNamesDWARFIndex.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_DEBUGNAMESDWARFINDEX_H
 #define LLDB_DEBUGNAMESDWARFINDEX_H
 
 #include "Plugins/SymbolFile/DWARF/DWARFIndex.h"
 #include "Plugins/SymbolFile/DWARF/LogChannelDWARF.h"
+#include "Plugins/SymbolFile/DWARF/ManualDWARFIndex.h"
 #include "lldb/Utility/ConstString.h"
 #include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
 
 namespace lldb_private {
 class DebugNamesDWARFIndex : public DWARFIndex {
 public:
   static llvm::Expected<std::unique_ptr<DebugNamesDWARFIndex>>
   Create(Module &module, DWARFDataExtractor debug_names,
          DWARFDataExtractor debug_str, DWARFDebugInfo *debug_info);
 
-  void Preload() override {}
+  void Preload() override { m_fallback.Preload(); }
 
   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,
                             DIEArray &offsets) override {}
public:
   void Dump(Stream &s) override;
 
 private:
   DebugNamesDWARFIndex(Module &module,
                        std::unique_ptr<llvm::DWARFDebugNames> debug_names_up,
                        DWARFDataExtractor debug_names_data,
                        DWARFDataExtractor debug_str_data,
                        DWARFDebugInfo *debug_info)
-      : DWARFIndex(module), m_debug_names_up(std::move(debug_names_up)) {}
+      : DWARFIndex(module), m_debug_names_up(std::move(debug_names_up)),
+        m_fallback(module, debug_info, GetUnits(*m_debug_names_up)) {}
 
   // LLVM DWARFDebugNames will hold a non-owning reference to this data, so keep
   // track of the ownership here.
   DWARFDataExtractor m_debug_names_data;
   DWARFDataExtractor m_debug_str_data;
 
   using DebugNames = llvm::DWARFDebugNames;
   std::unique_ptr<DebugNames> m_debug_names_up;
+  ManualDWARFIndex m_fallback;
 
   void Append(const DebugNames::Entry &entry, DIEArray &offsets);
   void MaybeLogLookupError(llvm::Error error, const DebugNames::NameIndex &ni,
                            llvm::StringRef name);
+
+  static llvm::DenseSet<dw_offset_t> GetUnits(const DebugNames &debug_names);
 };
 
 } // namespace lldb_private
 
 #endif // LLDB_DEBUGNAMESDWARFINDEX_H

lldb/trunk/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp

auto index_up =
       llvm::make_unique<DebugNames>(ToLLVM(debug_names), ToLLVM(debug_str));
   if (llvm::Error E = index_up->extract())
     return std::move(E);
 
   return std::unique_ptr<DebugNamesDWARFIndex>(new DebugNamesDWARFIndex(
       module, std::move(index_up), debug_names, debug_str, debug_info));
 }
 
+llvm::DenseSet<dw_offset_t>
+DebugNamesDWARFIndex::GetUnits(const DebugNames &debug_names) {
+  llvm::DenseSet<dw_offset_t> result;
+  for (const DebugNames::NameIndex &ni : debug_names) {
+    for (uint32_t cu = 0; cu < ni.getCUCount(); ++cu)
+      result.insert(ni.getCUOffset(cu));
+  }
+  return result;
+}
+
 void DebugNamesDWARFIndex::Append(const DebugNames::Entry &entry,
                                   DIEArray &offsets) {
   llvm::Optional<uint64_t> cu_offset = entry.getCUOffset();
   llvm::Optional<uint64_t> die_offset = entry.getDIESectionOffset();
   if (cu_offset && die_offset)
     offsets.emplace_back(*cu_offset, *die_offset);
 }
 
 void DebugNamesDWARFIndex::MaybeLogLookupError(llvm::Error error,
                                                const DebugNames::NameIndex &ni,
                                                llvm::StringRef name) {
   // Ignore SentinelErrors, log everything else.
   LLDB_LOG_ERROR(
       LogChannelDWARF::GetLogIfAll(DWARF_LOG_LOOKUPS),
       handleErrors(std::move(error), [](const DebugNames::SentinelError &) {}),
       "Failed to parse index entries for index at {1:x}, name {2}: {0}",
       ni.getUnitOffset(), name);
 }
 
 void DebugNamesDWARFIndex::GetGlobalVariables(ConstString basename,
                                               DIEArray &offsets) {
+  m_fallback.GetGlobalVariables(basename, offsets);
+
   for (const DebugNames::Entry &entry :
        m_debug_names_up->equal_range(basename.GetStringRef())) {
     if (entry.tag() != DW_TAG_variable)
       continue;
 
     Append(entry, offsets);
   }
 }
 
 void DebugNamesDWARFIndex::GetGlobalVariables(const RegularExpression &regex,
                                               DIEArray &offsets) {
+  m_fallback.GetGlobalVariables(regex, offsets);
+
   for (const DebugNames::NameIndex &ni: *m_debug_names_up) {
     for (DebugNames::NameTableEntry nte: ni) {
       if (!regex.Execute(nte.getString()))
         continue;
 
       uint32_t entry_offset = nte.getEntryOffset();
       llvm::Expected<DebugNames::Entry> entry_or = ni.getEntry(&entry_offset);
       for (; entry_or; entry_or = ni.getEntry(&entry_offset)) {
         if (entry_or->tag() != DW_TAG_variable)
           continue;
 
         Append(*entry_or, offsets);
       }
       MaybeLogLookupError(entry_or.takeError(), ni, nte.getString());
     }
   }
 }
 
 void DebugNamesDWARFIndex::Dump(Stream &s) {
+  m_fallback.Dump(s);
+
   std::string data;
   llvm::raw_string_ostream os(data);
   m_debug_names_up->dump(os);
   s.PutCString(os.str());
 }

lldb/trunk/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/NameToDIE.h"
+#include "llvm/ADT/DenseSet.h"
 
 namespace lldb_private {
 class ManualDWARFIndex : public DWARFIndex {
 public:
-  ManualDWARFIndex(Module &module, DWARFDebugInfo *debug_info)
-      : DWARFIndex(module), m_debug_info(debug_info) {}
+  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)) {}
 
   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;
private:
 
   static void
   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;
 
   IndexSet m_set;
 };
 } // namespace lldb_private
 
 #endif // LLDB_MANUALDWARFINDEX_H

lldb/trunk/source/Plugins/SymbolFile/DWARF/ManualDWARFIndex.cpp

if (!m_debug_info)
     return;
 
   DWARFDebugInfo &debug_info = *m_debug_info;
   m_debug_info = nullptr;
 
   static Timer::Category func_cat(LLVM_PRETTY_FUNCTION);
   Timer scoped_timer(func_cat, "%p", static_cast<void *>(&debug_info));
 
-  const uint32_t num_compile_units = debug_info.GetNumCompileUnits();
-  if (num_compile_units == 0)
+  std::vector<DWARFUnit *> units_to_index;
+  units_to_index.reserve(debug_info.GetNumCompileUnits());
+  for (size_t U = 0; U < debug_info.GetNumCompileUnits(); ++U) {
+    DWARFUnit *unit = debug_info.GetCompileUnitAtIndex(U);
+    if (unit && m_units_to_avoid.count(unit->GetOffset()) == 0)
+      units_to_index.push_back(unit);
+  }
+  if (units_to_index.empty())
     return;
 
-  std::vector<IndexSet> sets(num_compile_units);
+  std::vector<IndexSet> sets(units_to_index.size());
 
   //----------------------------------------------------------------------
   // Keep memory down by clearing DIEs for any compile units if indexing
   // caused us to load the compile unit's DIEs.
   //----------------------------------------------------------------------
-  std::vector<llvm::Optional<DWARFUnit::ScopedExtractDIEs>>
-      clear_cu_dies(num_compile_units);
+  std::vector<llvm::Optional<DWARFUnit::ScopedExtractDIEs>> clear_cu_dies(
+      units_to_index.size());
   auto parser_fn = [&](size_t cu_idx) {
-    DWARFUnit *dwarf_cu = debug_info.GetCompileUnitAtIndex(cu_idx);
-    if (dwarf_cu)
-      IndexUnit(*dwarf_cu, sets[cu_idx]);
+    IndexUnit(*units_to_index[cu_idx], sets[cu_idx]);
   };
 
-  auto extract_fn = [&debug_info, &clear_cu_dies](size_t cu_idx) {
-    DWARFUnit *dwarf_cu = debug_info.GetCompileUnitAtIndex(cu_idx);
-    if (dwarf_cu)
-      clear_cu_dies[cu_idx] = dwarf_cu->ExtractDIEsScoped();
+  auto extract_fn = [&units_to_index, &clear_cu_dies](size_t cu_idx) {
+    clear_cu_dies[cu_idx] = units_to_index[cu_idx]->ExtractDIEsScoped();
   };
 
   // Create a task runner that extracts dies for each DWARF compile unit in a
   // separate thread
   //----------------------------------------------------------------------
   // First figure out which compile units didn't have their DIEs already
   // parsed and remember this.  If no DIEs were parsed prior to this index
   // function call, we are going to want to clear the CU dies after we are
   // done indexing to make sure we don't pull in all DWARF dies, but we need
   // to wait until all compile units have been indexed in case a DIE in one
   // compile unit refers to another and the indexes accesses those DIEs.
   //----------------------------------------------------------------------
-  TaskMapOverInt(0, num_compile_units, extract_fn);
+  TaskMapOverInt(0, units_to_index.size(), extract_fn);
 
   // Now create a task runner that can index each DWARF compile unit in a
   // separate thread so we can index quickly.
 
-  TaskMapOverInt(0, num_compile_units, parser_fn);
+  TaskMapOverInt(0, units_to_index.size(), parser_fn);
 
   auto finalize_fn = [this, &sets](NameToDIE(IndexSet::*index)) {
     NameToDIE &result = m_set.*index;
     for (auto &set : sets)
       result.Append(set.*index);
     result.Finalize();
   };