Huge memory and performance improvements in the DWARF parser.

Address ranges are now split up into two different tables: 
- one in DWARFDebugInfo that is compile unit specific
- one in each DWARFCompileUnit that has exact function DIE offsets

This helps keep the size of the aranges down since the main table will get
uniqued and sorted and have consecutive ranges merged. We then only parse the
compile unit one on demand once we have determined that a compile unit contains
the address in question. We also now use the .debug_aranges section if there 
is one instead of always indexing the DWARF manually.

NameToDIE now uses a UniqueCStringMap<dw_offset> map instead of a std::map.
std::map is very bulky as each node has 3 pointers and the key and value types.
This gets our NameToDIE entry down to 12 bytes each instead of 48 which saves
us a lot of memory when we have very large DWARF.

DWARFDebugAranges now has a smaller footprint for each range it contains to 
save on memory.

llvm-svn: 139557

1 files changed, 27 insertions, 309 deletions

diff --git a/lldb/source/Plugins/SymbolFile/DWARF/NameToDIE.cpp b/lldb/source/Plugins/SymbolFile/DWARF/NameToDIE.cpp
index 5d25ccb5cf7..069009e62f3 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/NameToDIE.cpp
+++ b/lldb/source/Plugins/SymbolFile/DWARF/NameToDIE.cpp
@@ -23,335 +23,53 @@ using namespace lldb;
 using namespace lldb_private;
 
 void
-NameToDIE::Insert (const ConstString& name, const Info &info)
+NameToDIE::Finalize()
 {
-    m_collection.insert (std::make_pair(name.AsCString(), info));
+    m_map.Sort ();
+    m_map.SizeToFit ();
 }
 
-size_t
-NameToDIE::Find (const ConstString &name, std::vector<Info> &info_array) const
+void
+NameToDIE::Insert (const ConstString& name, uint32_t die_offset)
 {
-    const char *name_cstr = name.AsCString();
-    const size_t initial_info_array_size = info_array.size();
-    collection::const_iterator pos, end = m_collection.end();
-    for (pos = m_collection.lower_bound (name_cstr); pos != end && pos->first == name_cstr; ++pos)
-    {
-        info_array.push_back (pos->second);
-    }
-    return info_array.size() - initial_info_array_size;
+    m_map.Append(name.GetCString(), die_offset);
 }
 
 size_t
-NameToDIE::Find (const RegularExpression& regex, std::vector<Info> &info_array) const
+NameToDIE::Find (const ConstString &name, DIEArray &info_array) const
 {
-    const size_t initial_info_array_size = info_array.size();
-    collection::const_iterator pos, end = m_collection.end();
-    for (pos = m_collection.begin(); pos != end; ++pos)
-    {
-        if (regex.Execute(pos->first))
-            info_array.push_back (pos->second);
-    }
-    return info_array.size() - initial_info_array_size;
+    return m_map.GetValues (name.GetCString(), info_array);
 }
 
 size_t
-NameToDIE::FindAllEntriesForCompileUnitWithIndex (const uint32_t cu_idx, std::vector<Info> &info_array) const
+NameToDIE::Find (const RegularExpression& regex, DIEArray &info_array) const
 {
-    const size_t initial_info_array_size = info_array.size();
-    collection::const_iterator pos, end = m_collection.end();
-    for (pos = m_collection.begin(); pos != end; ++pos)
-    {
-        if (cu_idx == pos->second.cu_idx)
-            info_array.push_back (pos->second);
-    }
-    return info_array.size() - initial_info_array_size;
+    return m_map.GetValues (regex, info_array);
 }
 
-void
-NameToDIE::Dump (Stream *s)
+size_t
+NameToDIE::FindAllEntriesForCompileUnit (uint32_t cu_offset, 
+                                         uint32_t cu_end_offset, 
+                                         DIEArray &info_array) const
 {
-    collection::const_iterator pos, end = m_collection.end();
-    for (pos = m_collection.begin(); pos != end; ++pos)
+    const size_t initial_size = info_array.size();
+    const uint32_t size = m_map.GetSize();
+    for (uint32_t i=0; i<size; ++i)
     {
-        s->Printf("%p: 0x%8.8x 0x%8.8x \"%s\"\n", pos->first, pos->second.cu_idx, pos->second.die_idx, pos->first);
+        const uint32_t die_offset = m_map.GetValueAtIndexUnchecked(i);
+        if (cu_offset < die_offset && die_offset < cu_end_offset)
+            info_array.push_back (die_offset);
     }
+    return info_array.size() - initial_size;
 }
 
-
-static uint32_t
-dl_new_hash (const char *s)
-{
-    uint32_t h = 5381;
-    
-    for (unsigned char c = *s; c; c = *++s)
-        h = ((h << 5) + h) + c;
-    
-    return h;
-}
-
-struct HashEntry
-{
-    uint32_t hash;
-    uint32_t cu_idx;
-    uint32_t die_idx;
-    const char *name;
-    
-    bool
-    operator < (const HashEntry &rhs) const
-    {
-        return hash < rhs.hash;
-    }
-};
-
-struct HashHeader
-{
-    uint32_t version;
-    uint32_t bucket_info_size; // The fixed data associated with this bucket
-    uint32_t bucket_count;
-    uint32_t flags;
-};
-
-struct HashBucketInfo
-{
-    uint32_t offset;    // Offset to the data for each bucket
-};
-
-struct HashBucketEntryStrp
-{
-    HashBucketEntryStrp () :
-        str_offset (0)
-    {
-    }
-
-    HashBucketEntryStrp (uint32_t s, uint32_t d) :
-        str_offset (s)
-    {
-    }
-    
-    uint32_t
-    GetByteSize ()
-    {
-        return  sizeof(uint32_t) + // String offset in .debug_str
-                sizeof(uint32_t) + // Number of dies
-                die_array.size() * sizeof(uint32_t);
-    }
-
-    uint32_t str_offset;
-    std::vector<dw_offset_t> die_array;
-};
-
-typedef std::vector<dw_offset_t> DIEArray;
-typedef std::map<const char *, DIEArray> NameToDIEArrayMap;
-
-struct HashBucketEntryCStr
+void
+NameToDIE::Dump (Stream *s)
 {
-    uint32_t
-    GetByteSize () const
+    const uint32_t size = m_map.GetSize();
+    for (uint32_t i=0; i<size; ++i)
     {
-        uint32_t byte_size = 0;
-        NameToDIEArrayMap::const_iterator pos, end = name_to_die.end();
-        for (pos = name_to_die.begin(); pos != end; ++pos)
-        {
-            // Include the size of the and a length for the dies, and all dies
-            byte_size += sizeof(uint32_t) + sizeof(uint32_t) * (pos->second.size() + 1);
-        }
-        return byte_size;
+        const char *cstr = m_map.GetCStringAtIndex(i);
+        s->Printf("%p: {0x%8.8x} \"%s\"\n", cstr, m_map.GetValueAtIndexUnchecked(i), cstr);
     }
-    
-    NameToDIEArrayMap name_to_die;
-};
-
-static uint32_t
-closest_power_2_less_than_n (uint32_t n)
-{  
-    if (n)
-        return 0x80000000u >> __builtin_clz (n);
-    return 0;
-}
-
-typedef struct HashEntry HashEntryType;
-
-void
-NameToDIE::Hash (Stream *s, SymbolFileDWARF *dwarf)
-{
-//    if (m_collection.empty())
-//        return;
-//    
-//    typedef std::vector<HashEntryType> hash_collection;
-//    hash_collection hash_entries;
-//    collection::const_iterator pos, end = m_collection.end();
-//    for (pos = m_collection.begin(); pos != end; ++pos)
-//    {
-//        HashEntry entry = { dl_new_hash (pos->first), pos->second.cu_idx, pos->second.die_idx, pos->first };
-//        hash_entries.push_back (entry); 
-//    }
-//    
-////    const DataExtractor &debug_str_data = dwarf->get_debug_str_data();
-//    
-////    uint32_t collisions = 0;
-////    for (i=1; i<hash_entries_size; ++i)
-////    {
-////        if (hash_entries[i-1].hash == hash_entries[i].hash &&
-////            hash_entries[i-1].name != hash_entries[i].name)
-////            ++collisions;
-////    }
-////    s->Printf("count = %u, collisions = %u\n", hash_entries_size, collisions);
-//    
-////    for (i=0; i<hash_entries_size; ++i)
-////        s->Printf("0x%8.8x: cu = %8u, die = %8u, name = '%s'\n", 
-////                  hash_entries[i].hash,
-////                  hash_entries[i].cu_idx,
-////                  hash_entries[i].die_idx,
-////                  hash_entries[i].name);
-//    DWARFDebugInfo *debug_info = dwarf->DebugInfo();
-//
-//    uint32_t num_buckets;
-//    if (hash_entries_size > 1024)
-//        num_buckets = closest_power_2_less_than_n (hash_entries_size/16);
-//    else if (hash_entries_size > 128)
-//        num_buckets = closest_power_2_less_than_n (hash_entries_size/8);
-//    else
-//        num_buckets = closest_power_2_less_than_n (hash_entries_size/4);
-//    if (num_buckets == 0)
-//        num_buckets = 1;
-//    
-//    //for (uint32_t power_2 = 0x10; power_2 <= hash_entries_size; power_2 <<= 1)
-//    {
-////        if (num_buckets > 0x10 && num_buckets > hash_entries_size)
-////            break;
-//
-//        typedef std::vector<uint32_t> uint32_array;
-//        typedef std::map<uint32_t, HashBucketEntryCStr> HashBucketEntryMap;
-//        std::vector<HashBucketEntryMap> hash_buckets;
-//        hash_buckets.resize(num_buckets);
-//        
-//        uint32_t bucket_entry_empties = 0;
-//        uint32_t bucket_entry_single = 0;
-//        uint32_t bucket_entry_collisions = 0;
-//        uint32_t names_entry_single = 0;
-//        uint32_t names_entry_collisions = 0;
-//        //StreamString hash_file_data(Stream::eBinary, dwarf->GetObjectFile()->GetAddressByteSize(), dwarf->GetObjectFile()->GetByteSize());
-//
-//        // Write hash table header
-////        hash_file_data.PutHex32 (1); // Version
-////        hash_file_data.PutHex32 (4); // Sizeof bucket data
-////        hash_file_data.PutHex32 (num_buckets);
-////        hash_file_data.PutHex32 (0); // Flags
-//        
-//        s->Printf("HashHeader = { version = %u, bucket_info_size = %u, bucket_count = %u, flags = 0x%8.8x }\n", 1, (uint32_t)sizeof(HashBucketInfo), num_buckets, 0);
-//        
-//        for (i=0; i<hash_entries_size; ++i)
-//        {
-//            uint32_t hash = hash_entries[i].hash;
-//            uint32_t bucket_idx = hash_entries[i].hash % num_buckets;
-//            DWARFCompileUnit *cu = debug_info->GetCompileUnitAtIndex (hash_entries[i].cu_idx);
-//            cu->ExtractDIEsIfNeeded(false);
-//            DWARFDebugInfoEntry *die = cu->GetDIEAtIndexUnchecked(hash_entries[i].die_idx);
-//            hash_buckets[bucket_idx][hash].name_to_die[hash_entries[i].name].push_back(die->GetOffset());
-//        }
-//        uint32_t byte_size = sizeof(HashHeader); // Header
-//        uint32_t data_offset = 0;
-//        uint32_t num_bucket_entries;
-//        uint32_t bucket_data_size;
-//        // Now for each bucket we write the offset to the data for each bucket
-//        // The offset is currently a zero based offset from the end of this table
-//        // which is header.num_buckets * sizeof(uint32_t) long.
-//        for (i=0; i<num_buckets; ++i)
-//        {
-//            byte_size += sizeof(HashBucketInfo);
-//            HashBucketEntryMap &bucket_entry = hash_buckets[i];
-//            bucket_data_size = 0;
-//            HashBucketEntryMap::const_iterator pos, end = bucket_entry.end();
-//            for (pos = bucket_entry.begin(); pos != end; ++pos)
-//            {
-//                bucket_data_size += sizeof(pos->first) + pos->second.GetByteSize();
-//            }
-//            if (bucket_data_size > 0)
-//            {
-//                // Offset to bucket data
-////                hash_file_data.PutHex32 (data_offset); 
-//                s->Printf("bucket[%u] {0x%8.8x}\n", i, data_offset);
-//                data_offset += bucket_data_size;
-//            }
-//            else
-//            {
-//                // Invalid offset that indicates an empty bucket
-////                hash_file_data.PutHex32 (UINT32_MAX);
-//                s->Printf("bucket[%u] {0xFFFFFFFF}\n", i);
-//                ++bucket_entry_empties;
-//            }
-//        }
-//
-//        // Now we write the bucket data for each bucket that corresponds to each bucket
-//        // offset from above.
-//        data_offset = 0;
-//        uint32_t total_num_name_entries = 0;
-//        uint32_t total_num_bucket_entries = 0;
-//        uint32_t total_non_empty_buckets = 0;
-//        for (i=0; i<num_buckets; ++i)
-//        {
-//            HashBucketEntryMap &bucket_entry = hash_buckets[i];
-//            bucket_data_size = 0;
-//            if (bucket_entry.empty())
-//                continue;
-//
-//            ++total_non_empty_buckets;
-//            
-//            s->Printf("0x%8.8x: BucketEntry:\n", data_offset, num_bucket_entries);                
-//            bucket_data_size = 0;
-//            uint32_t num_bucket_entries = 0;
-//            HashBucketEntryMap::const_iterator pos, end = bucket_entry.end();
-//            for (pos = bucket_entry.begin(); pos != end; ++pos)
-//            {
-//                ++num_bucket_entries;
-//                uint32_t hash_data_len = pos->second.GetByteSize();
-//                s->Printf("  hash = 0x%8.8x, length = 0x%8.8x:\n", pos->first, hash_data_len);
-////                hash_file_data.PutHex32 (pos->first); // Write the hash
-////                hash_file_data.PutHex32 (hash_data_len); // The length of the data for this hash not including the length itself
-//                
-//                const HashBucketEntryCStr &hash_entry = pos->second;
-//                uint32_t num_name_entries = 0;
-//                NameToDIEArrayMap::const_iterator name_pos, name_end = hash_entry.name_to_die.end();
-//                for (name_pos = hash_entry.name_to_die.begin(); name_pos != name_end; ++name_pos)
-//                {
-//                    ++num_name_entries;
-//                    ++total_num_name_entries;
-//                    s->Printf("    name = %p '%s'\n", name_pos->first, name_pos->first);
-////                    hash_file_data.PutHex32 (pos->first); // Write the hash
-////                    hash_file_data.PutHex32 (hash_data_len); // The length of the data for this hash not including the length itself
-//
-//
-//                    const uint32_t num_dies = name_pos->second.size();
-//                    s->Printf("      dies[%u] = { ", num_dies);
-//                    for (uint32_t j=0; j < num_dies; ++j)
-//                        s->Printf("0x%8.8x ", name_pos->second[j]);
-//                    s->PutCString("}\n");
-//                }
-//                if (num_name_entries == 1)
-//                    ++names_entry_single;
-//                else if (num_name_entries > 1)
-//                    ++names_entry_collisions;
-//                bucket_data_size += sizeof(pos->first) + hash_data_len;
-//            }
-//            data_offset += bucket_data_size;
-//            byte_size += bucket_data_size;
-//            total_num_bucket_entries += num_bucket_entries;
-//            if (num_bucket_entries == 1)
-//                ++bucket_entry_single;
-//            else if (num_bucket_entries > 1)
-//                ++bucket_entry_collisions;
-//        }
-//
-//        s->Printf ("Trying size of %u buckets, %u items:\n", num_buckets, hash_entries_size);
-//        s->Printf ("buckets: empty    = %u (%%%f)\n", bucket_entry_empties, ((float)bucket_entry_empties/(float)num_buckets) * 100.0f);
-//        s->Printf ("buckets: single   = %u\n", bucket_entry_single);
-//        s->Printf ("buckets: multiple = %u (avg = %f entries/bucket, avg = %f entries/non-empty bucket)\n",
-//                   bucket_entry_collisions, 
-//                   (float)total_num_bucket_entries / (float)num_buckets,
-//                   (float)total_num_bucket_entries / (float)total_non_empty_buckets);
-//        s->Printf ("names  : single   = %u of %u\n", names_entry_single, total_num_name_entries);
-//        s->Printf ("names  : multiple = %u of %u\n", names_entry_collisions, total_num_name_entries);
-//        s->Printf ("total byte size   = %u\n", byte_size);
-//        s->PutCString ("\n----------------------------------------------------------------------\n\n");
-//    }
 }