Further performance improvements in the DWARF parser:

1 - the DIE collections no longer have the NULL tags which saves up to 25%
    of the memory on typical C++ code
2 - faster parsing by not having to run the SetDIERelations() function anymore
    it is done when parsing the DWARF very efficiently.

llvm-svn: 144983

1 files changed, 54 insertions, 124 deletions

diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DWARFCompileUnit.cpp b/lldb/source/Plugins/SymbolFile/DWARF/DWARFCompileUnit.cpp
index 8c521751a49..aa8699f0ad2 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/DWARFCompileUnit.cpp
+++ b/lldb/source/Plugins/SymbolFile/DWARF/DWARFCompileUnit.cpp
@@ -28,6 +28,7 @@ using namespace lldb;
 using namespace lldb_private;
 using namespace std;
 
+
 extern int g_verbose;
 
 DWARFCompileUnit::DWARFCompileUnit(SymbolFileDWARF* dwarf2Data) :
@@ -176,7 +177,10 @@ DWARFCompileUnit::ExtractDIEsIfNeeded (bool cu_die_only)
     // We are in our compile unit, parse starting at the offset
     // we were told to parse
     const DataExtractor& debug_info_data = m_dwarf2Data->get_debug_info_data();
-
+    std::vector<uint32_t> die_index_stack;
+    die_index_stack.reserve(32);
+    die_index_stack.push_back(0);
+    bool prev_die_had_children = false;
     const uint8_t *fixed_form_sizes = DWARFFormValue::GetFixedFormSizesForAddressSize (GetAddressByteSize());
     while (offset < next_cu_offset &&
            die.FastExtract (debug_info_data, this, fixed_form_sizes, &offset))
@@ -188,43 +192,70 @@ DWARFCompileUnit::ExtractDIEsIfNeeded (bool cu_die_only)
 //                        DW_TAG_value_to_name (die.Tag()),
 //                        die.HasChildren() ? " *" : "");
 
+        const bool null_die = die.IsNULL();
         if (depth == 0)
         {
             uint64_t base_addr = die.GetAttributeValueAsUnsigned(m_dwarf2Data, this, DW_AT_low_pc, LLDB_INVALID_ADDRESS);
             if (base_addr == LLDB_INVALID_ADDRESS)
                 base_addr = die.GetAttributeValueAsUnsigned(m_dwarf2Data, this, DW_AT_entry_pc, 0);
             SetBaseAddress (base_addr);
-        }
-
-        if (cu_die_only)
-        {
-            AddDIE (die);
-            return 1;
-        }
-        else if (depth == 0 && initial_die_array_size == 1)
-        {
-            // Don't append the CU die as we already did that
+            if (initial_die_array_size == 0)
+                AddDIE (die);
+            if (cu_die_only)
+                return 1;
         }
         else
         {
-            AddDIE (die);
+            if (null_die)
+            {
+                if (prev_die_had_children)
+                {
+                    // This will only happen if a DIE says is has children
+                    // but all it contains is a NULL tag. Since we are removing
+                    // the NULL DIEs from the list (saves up to 25% in C++ code),
+                    // we need a way to let the DIE know that it actually doesn't
+                    // have children.
+                    if (!m_die_array.empty())
+                        m_die_array.back().SetEmptyChildren(true);
+                }
+            }
+            else
+            {
+                die.SetParentIndex(m_die_array.size() - die_index_stack[depth-1]);
+
+                if (die_index_stack.back())
+                    m_die_array[die_index_stack.back()].SetSiblingIndex(m_die_array.size()-die_index_stack.back());
+                
+                // Only push the DIE if it isn't a NULL DIE
+                    m_die_array.push_back(die);
+            }
         }
 
-        if (die.IsNULL())
+        if (null_die)
         {
             // NULL DIE.
+            if (!die_index_stack.empty())
+                die_index_stack.pop_back();
+
             if (depth > 0)
                 --depth;
             if (depth == 0)
                 break;  // We are done with this compile unit!
+
+            prev_die_had_children = false;
         }
         else
         {
+            die_index_stack.back() = m_die_array.size() - 1;
             // Normal DIE
-            if (die.HasChildren())
+            const bool die_has_children = die.HasChildren();
+            if (die_has_children)
+            {
+                die_index_stack.push_back(0);
                 ++depth;
+            }
+            prev_die_had_children = die_has_children;
         }
-
     }
 
     // Give a little bit of info if we encounter corrupt DWARF (our offset
@@ -240,8 +271,15 @@ DWARFCompileUnit::ExtractDIEsIfNeeded (bool cu_die_only)
         }
         fprintf (stderr, "warning: DWARF compile unit extends beyond its bounds cu 0x%8.8x at 0x%8.8x in '%s'\n", GetOffset(), offset, path);
     }
+    
+    LogSP log (LogChannelDWARF::GetLogIfAll (DWARF_LOG_DEBUG_INFO));
+    if (log)
+    {
+        StreamString strm;
+        DWARFDebugInfoEntry::DumpDIECollection (strm, m_die_array);
+        log->PutCString (strm.GetString().c_str());
+    }
 
-    SetDIERelations();
     return m_die_array.size();
 }
 
@@ -406,114 +444,6 @@ DWARFCompileUnit::LookupAddress
 }
 
 //----------------------------------------------------------------------
-// SetDIERelations()
-//
-// We read in all of the DIE entries into our flat list of DIE entries
-// and now we need to go back through all of them and set the parent,
-// sibling and child pointers for quick DIE navigation.
-//----------------------------------------------------------------------
-void
-DWARFCompileUnit::SetDIERelations()
-{
-#if 0
-    // Compute average bytes per DIE
-    //
-    // We can figure out what the average number of bytes per DIE is
-    // to help us pre-allocate the correct number of m_die_array
-    // entries so we don't end up doing a lot of memory copies as we
-    // are creating our DIE array when parsing
-    //
-    // Enable this code by changing "#if 0" above to "#if 1" and running
-    // the dsymutil or dwarfdump with a bunch of dwarf files and see what
-    // the running average ends up being in the stdout log.
-    static size_t g_total_cu_debug_info_size = 0;
-    static size_t g_total_num_dies = 0;
-    static size_t g_min_bytes_per_die = UINT32_MAX;
-    static size_t g_max_bytes_per_die = 0;
-    const size_t num_dies = m_die_array.size();
-    const size_t cu_debug_info_size = GetDebugInfoSize();
-    const size_t bytes_per_die = cu_debug_info_size / num_dies;
-    if (g_min_bytes_per_die > bytes_per_die)
-        g_min_bytes_per_die = bytes_per_die;
-    if (g_max_bytes_per_die < bytes_per_die)
-        g_max_bytes_per_die = bytes_per_die;
-    if (g_total_cu_debug_info_size == 0)
-    {
-        cout << "                    min max avg" << endl
-             << "n dies cu size  bpd bpd bpd bpd" << endl
-             << "------ -------- --- === === ===" << endl;
-    }
-    g_total_cu_debug_info_size += cu_debug_info_size;
-    g_total_num_dies += num_dies;
-    const size_t avg_bytes_per_die = g_total_cu_debug_info_size / g_total_num_dies;
-    cout
-        << DECIMAL_WIDTH(6) << num_dies << ' '
-        << DECIMAL_WIDTH(8) << cu_debug_info_size  << ' '
-        << DECIMAL_WIDTH(3) << bytes_per_die << ' '
-        << DECIMAL_WIDTH(3) << g_min_bytes_per_die << ' '
-        << DECIMAL_WIDTH(3) << g_max_bytes_per_die << ' '
-        << DECIMAL_WIDTH(3) << avg_bytes_per_die
-        << endl;
-#endif
-    if (m_die_array.empty())
-        return;
-    DWARFDebugInfoEntry* die_array_begin = &m_die_array.front();
-    DWARFDebugInfoEntry* die_array_end = &m_die_array.back();
-    DWARFDebugInfoEntry* curr_die;
-    // We purposely are skipping the last element in the array in the loop below
-    // so that we can always have a valid next item
-    for (curr_die = die_array_begin;  curr_die < die_array_end;  ++curr_die)
-    {
-        // Since our loop doesn't include the last element, we can always
-        // safely access the next die in the array.
-        DWARFDebugInfoEntry* next_die = curr_die + 1;
-
-        if (curr_die->IsNULL())
-        {
-            // NULL DIE that terminates a sibling chain
-            DWARFDebugInfoEntry* parent = curr_die->GetParent();
-            if (parent)
-                parent->SetSibling(next_die);
-        }
-        else
-        {
-            // Normal DIE
-            if (curr_die->HasChildren())
-                next_die->SetParent(curr_die);
-            else
-                curr_die->SetSibling(next_die);
-        }
-    }
-
-    // Since we skipped the last element, we need to fix it up!
-    if (die_array_begin < die_array_end)
-        curr_die->SetParent(die_array_begin);
-
-#if 0
-    // The code below will dump the DIE relations in case any modification
-    // is done to the above code. This dump can be used in a diff to make
-    // sure that no functionality is lost.
-    {
-        DWARFDebugInfoEntry::const_iterator pos;
-        DWARFDebugInfoEntry::const_iterator end = m_die_array.end();
-        puts("offset    parent   sibling  child");
-        puts("--------  -------- -------- --------");
-        for (pos = m_die_array.begin(); pos != end; ++pos)
-        {
-            const DWARFDebugInfoEntry& die_ref = *pos;
-            const DWARFDebugInfoEntry* p = die_ref.GetParent();
-            const DWARFDebugInfoEntry* s = die_ref.GetSibling();
-            const DWARFDebugInfoEntry* c = die_ref.GetFirstChild();
-            printf("%.8x: %.8x %.8x %.8x\n", die_ref.GetOffset(),
-                p ? p->GetOffset() : 0,
-                s ? s->GetOffset() : 0,
-                c ? c->GetOffset() : 0);
-        }
-    }
-#endif
-
-}
-//----------------------------------------------------------------------
 // Compare function DWARFDebugAranges::Range structures
 //----------------------------------------------------------------------
 static bool CompareDIEOffset (const DWARFDebugInfoEntry& die1, const DWARFDebugInfoEntry& die2)