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

5 files changed, 135 insertions, 138 deletions

diff --git a/lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.cpp b/lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.cpp
index 6aa89fadaa9..e8e5aac7b01 100644
--- a/lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.cpp
+++ b/lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.cpp
@@ -773,7 +773,7 @@ ProcessGDBRemote::DoAttachToProcessWithID (lldb::pid_t attach_pid)
         {
             char packet[64];
             const int packet_len = ::snprintf (packet, sizeof(packet), "vAttach;%x", attach_pid);
-            
+            SetID (attach_pid);            
             m_async_broadcaster.BroadcastEvent (eBroadcastBitAsyncContinue, new EventDataBytes (packet, packet_len));
         }
     }
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)
diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DWARFCompileUnit.h b/lldb/source/Plugins/SymbolFile/DWARF/DWARFCompileUnit.h
index e54c6bc68f7..49b05d14473 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/DWARFCompileUnit.h
+++ b/lldb/source/Plugins/SymbolFile/DWARF/DWARFCompileUnit.h
@@ -55,9 +55,6 @@ public:
         m_base_addr = base_addr;
     }
 
-    void
-    SetDIERelations();
-
     const DWARFDebugInfoEntry*
     GetCompileUnitDIEOnly()
     {
diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugInfoEntry.cpp b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugInfoEntry.cpp
index 891f7b4b023..0d2adb05cf9 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugInfoEntry.cpp
+++ b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugInfoEntry.cpp
@@ -112,11 +112,13 @@ DWARFDebugInfoEntry::FastExtract
 )
 {
     m_offset = *offset_ptr;
-
+    m_parent_idx = 0;
+    m_sibling_idx = 0;
+    m_empty_children = false;
     uint64_t abbr_idx = debug_info_data.GetULEB128 (offset_ptr);
     assert (abbr_idx < (1 << DIE_ABBR_IDX_BITSIZE));
     m_abbr_idx = abbr_idx;
-
+    
     assert (fixed_form_sizes);  // For best performance this should be specified!
     
     if (m_abbr_idx)
@@ -1919,3 +1921,28 @@ DWARFDebugInfoEntry::OffsetLessThan (const DWARFDebugInfoEntry& a, const DWARFDe
     return a.GetOffset() < b.GetOffset();
 }
 
+void
+DWARFDebugInfoEntry::DumpDIECollection (Stream &strm, DWARFDebugInfoEntry::collection &die_collection)
+{
+    DWARFDebugInfoEntry::const_iterator pos;
+    DWARFDebugInfoEntry::const_iterator end = die_collection.end();
+    puts("offset    parent   sibling  child");
+    puts("--------  -------- -------- --------");
+    for (pos = die_collection.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();
+        strm.Printf("%.8x: %.8x %.8x %.8x 0x%4.4x %s%s\n", 
+                    die_ref.GetOffset(),
+                    p ? p->GetOffset() : 0,
+                    s ? s->GetOffset() : 0,
+                    c ? c->GetOffset() : 0,
+                    die_ref.Tag(), 
+                    DW_TAG_value_to_name(die_ref.Tag()),
+                    die_ref.HasChildren() ? " *" : "");
+    }
+}
+
+
diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugInfoEntry.h b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugInfoEntry.h
index 6e8a921bb9f..f97ad88eb39 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugInfoEntry.h
+++ b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDebugInfoEntry.h
@@ -41,6 +41,7 @@ typedef std::multimap<uint32_t, const DWARFDebugInfoEntry*> UInt32ToDIEMMap;
 typedef UInt32ToDIEMMap::iterator                           UInt32ToDIEMMapIter;
 typedef UInt32ToDIEMMap::const_iterator                     UInt32ToDIEMMapConstIter;
 
+#define DIE_SIBLING_IDX_BITSIZE 31
 #define DIE_ABBR_IDX_BITSIZE 15
 
 class DWARFDebugInfoEntry
@@ -107,11 +108,24 @@ public:
                     m_offset        (DW_INVALID_OFFSET),
                     m_parent_idx    (0),
                     m_sibling_idx   (0),
+                    m_empty_children(false),
                     m_abbr_idx      (0),
-                    m_has_children  (false)
+                    m_has_children  (false),
+                    m_tag           (0)
                 {
                 }
 
+    void        Clear ()
+                {
+                    m_offset         = DW_INVALID_OFFSET;
+                    m_parent_idx     = 0;
+                    m_sibling_idx    = 0;
+                    m_empty_children = false;
+                    m_abbr_idx       = 0;
+                    m_has_children   = false;
+                    m_tag            = 0;
+                }
+
     bool        Contains (const DWARFDebugInfoEntry *die) const;
 
     void        BuildAddressRangeTable(
@@ -323,8 +337,8 @@ public:
             // We know we are kept in a vector of contiguous entries, so we know
             // we don't need to store our child pointer, if we have a child it will
             // be the next entry in the list...
-            DWARFDebugInfoEntry*    GetFirstChild()         { return HasChildren() ? this + 1 : NULL; }
-    const   DWARFDebugInfoEntry*    GetFirstChild() const   { return HasChildren() ? this + 1 : NULL; }
+            DWARFDebugInfoEntry*    GetFirstChild()         { return (HasChildren() && !m_empty_children) ? this + 1 : NULL; }
+    const   DWARFDebugInfoEntry*    GetFirstChild() const   { return (HasChildren() && !m_empty_children) ? this + 1 : NULL; }
 
     void        
     SetParent (DWARFDebugInfoEntry* parent)     
@@ -352,13 +366,42 @@ public:
             m_sibling_idx = 0;
     }
 
+    void
+    SetSiblingIndex (uint32_t idx)
+    {
+        m_sibling_idx = idx;
+    }
+    
+    void
+    SetParentIndex (uint32_t idx)
+    {
+        m_parent_idx = idx;
+    }
+
+    bool
+    GetEmptyChildren () const
+    {
+        return m_empty_children;
+    }
+
+    void
+    SetEmptyChildren (bool b)
+    {
+        m_empty_children = b;
+    }
+
+    static void
+    DumpDIECollection (lldb_private::Stream &strm,
+                       DWARFDebugInfoEntry::collection &die_collection);
+
 protected:
-    dw_offset_t m_offset;       // Offset within the .debug_info of the start of this entry
-    uint32_t    m_parent_idx;   // How many to subtract from "this" to get the parent. If zero this die has no parent
-    uint32_t    m_sibling_idx;  // How many to add to "this" to get the sibling.
+    dw_offset_t m_offset;           // Offset within the .debug_info of the start of this entry
+    uint32_t    m_parent_idx;       // How many to subtract from "this" to get the parent. If zero this die has no parent
+    uint32_t    m_sibling_idx:31,   // How many to add to "this" to get the sibling.
+                m_empty_children:1; // If a DIE says it had children, yet it just contained a NULL tag, this will be set.
     uint32_t    m_abbr_idx:DIE_ABBR_IDX_BITSIZE,
-                m_has_children:1,
-                m_tag:16;
+                m_has_children:1,   // Set to 1 if this DIE has children
+                m_tag:16;           // A copy of the DW_TAG value so we don't have to go through the compile unit abbrev table
                 
 };