Fix record layout when synthesizing class types.

Prior to this patch, we would try to synthesize class types by
iterating over a DenseMap of FieldDecls and adding each one to
a CXXRecordDecl.  Since a DenseMap doesn't provide a deterministic
ordering of the elements, this would not add the fields in
FieldOffset order, but rather in some random order determined by
the memory layout of the DenseMap.

This patch fixes the issue by changing DenseMaps to vectors.  The
ability to lookup a value in the DenseMap was hardly being used,
and where it is sufficient to do a vector lookup.

Differential Revision: http://reviews.llvm.org/D8512

llvm-svn: 233090

1 files changed, 35 insertions, 49 deletions

diff --git a/lldb/source/Expression/ClangASTSource.cpp b/lldb/source/Expression/ClangASTSource.cpp
index dacd4cc57a6..8a39b7a38b5 100644
--- a/lldb/source/Expression/ClangASTSource.cpp
+++ b/lldb/source/Expression/ClangASTSource.cpp
@@ -1532,46 +1532,37 @@ ClangASTSource::FindObjCPropertyAndIvarDecls (NameSearchContext &context)
     while(0);
 }
 
-typedef llvm::DenseMap <const FieldDecl *, uint64_t> FieldOffsetMap;
-typedef llvm::DenseMap <const CXXRecordDecl *, CharUnits> BaseOffsetMap;
-
 template <class D, class O>
 static bool
-ImportOffsetMap (llvm::DenseMap <const D*, O> &destination_map,
-                 llvm::DenseMap <const D*, O> &source_map,
-                 ClangASTImporter *importer,
+ImportOffsetList(std::vector<std::pair<const D *, O>> &destination_list,
+                 const std::vector<std::pair<const D *, O>> &source_list, ClangASTImporter *importer,
                  ASTContext &dest_ctx)
 {
-    typedef llvm::DenseMap <const D*, O> MapType;
+    typedef std::vector<std::pair<const D *, O>> ListType;
 
-    for (typename MapType::iterator fi = source_map.begin(), fe = source_map.end();
-         fi != fe;
-         ++fi)
+    for (const auto &fi : source_list)
     {
-        DeclFromUser <D> user_decl(const_cast<D*>(fi->first));
+        DeclFromUser<D> user_decl(const_cast<D *>(fi.first));
         DeclFromParser <D> parser_decl(user_decl.Import(importer, dest_ctx));
         if (parser_decl.IsInvalid())
             return false;
-        destination_map.insert(std::pair<const D *, O>(parser_decl.decl, fi->second));
+        destination_list.push_back(std::pair<const D *, O>(parser_decl.decl, fi.second));
     }
 
     return true;
 }
 
-template <bool IsVirtual> bool ExtractBaseOffsets (const ASTRecordLayout &record_layout,
-                                                   DeclFromUser<const CXXRecordDecl> &record,
-                                                   BaseOffsetMap &base_offsets)
+template <bool IsVirtual>
+bool
+ExtractBaseOffsets(const ASTRecordLayout &record_layout, DeclFromUser<const CXXRecordDecl> &record,
+                   ClangASTSource::BaseOffsetList &base_offsets)
 {
-    for (CXXRecordDecl::base_class_const_iterator
-            bi = (IsVirtual ? record->vbases_begin() : record->bases_begin()),
-            be = (IsVirtual ? record->vbases_end() : record->bases_end());
-         bi != be;
-         ++bi)
+    for (const auto &base : (IsVirtual ? record->vbases() : record->bases()))
     {
-        if (!IsVirtual && bi->isVirtual())
+        if (!IsVirtual && base.isVirtual())
             continue;
 
-        const clang::Type *origin_base_type = bi->getType().getTypePtr();
+        const clang::Type *origin_base_type = base.getType().getTypePtr();
         const clang::RecordType *origin_base_record_type = origin_base_type->getAs<RecordType>();
 
         if (!origin_base_record_type)
@@ -1594,19 +1585,16 @@ template <bool IsVirtual> bool ExtractBaseOffsets (const ASTRecordLayout &record
         else
             base_offset = record_layout.getBaseClassOffset(origin_base_cxx_record.decl);
 
-        base_offsets.insert(std::pair<const CXXRecordDecl *, CharUnits>(origin_base_cxx_record.decl, base_offset));
+        base_offsets.push_back(std::make_pair(origin_base_cxx_record.decl, base_offset));
     }
 
     return true;
 }
 
 bool
-ClangASTSource::layoutRecordType(const RecordDecl *record,
-                                 uint64_t &size,
-                                 uint64_t &alignment,
-                                 FieldOffsetMap &field_offsets,
-                                 BaseOffsetMap &base_offsets,
-                                 BaseOffsetMap &virtual_base_offsets)
+ClangASTSource::layoutRecordType(const RecordDecl *record, uint64_t &size, uint64_t &alignment,
+                                 FieldOffsetList &field_offsets, BaseOffsetList &base_offsets,
+                                 BaseOffsetList &virtual_base_offsets)
 {
     ClangASTMetrics::RegisterRecordLayout();
 
@@ -1627,9 +1615,9 @@ ClangASTSource::layoutRecordType(const RecordDecl *record,
     if (origin_record.IsInvalid())
         return false;
 
-    FieldOffsetMap origin_field_offsets;
-    BaseOffsetMap origin_base_offsets;
-    BaseOffsetMap origin_virtual_base_offsets;
+    FieldOffsetList origin_field_offsets;
+    BaseOffsetList origin_base_offsets;
+    BaseOffsetList origin_virtual_base_offsets;
 
     ClangASTContext::GetCompleteDecl(&origin_record->getASTContext(), const_cast<RecordDecl*>(origin_record.decl));
 
@@ -1640,16 +1628,15 @@ ClangASTSource::layoutRecordType(const RecordDecl *record,
 
     int field_idx = 0, field_count = record_layout.getFieldCount();
 
-    for (RecordDecl::field_iterator fi = origin_record->field_begin(), fe = origin_record->field_end();
-         fi != fe;
-         ++fi)
+    origin_field_offsets.reserve(field_count);
+    for (const auto &field : origin_record->fields())
     {
         if (field_idx >= field_count)
             return false; // Layout didn't go well.  Bail out.
 
         uint64_t field_offset = record_layout.getFieldOffset(field_idx);
 
-        origin_field_offsets.insert(std::pair<const FieldDecl *, uint64_t>(*fi, field_offset));
+        origin_field_offsets.push_back(std::pair<const FieldDecl *, uint64_t>(field, field_offset));
 
         field_idx++;
     }
@@ -1665,9 +1652,9 @@ ClangASTSource::layoutRecordType(const RecordDecl *record,
             return false;
     }
 
-    if (!ImportOffsetMap(field_offsets, origin_field_offsets, m_ast_importer, parser_ast_context) ||
-        !ImportOffsetMap(base_offsets, origin_base_offsets, m_ast_importer, parser_ast_context) ||
-        !ImportOffsetMap(virtual_base_offsets, origin_virtual_base_offsets, m_ast_importer, parser_ast_context))
+    if (!ImportOffsetList(field_offsets, origin_field_offsets, m_ast_importer, parser_ast_context) ||
+        !ImportOffsetList(base_offsets, origin_base_offsets, m_ast_importer, parser_ast_context) ||
+        !ImportOffsetList(virtual_base_offsets, origin_virtual_base_offsets, m_ast_importer, parser_ast_context))
         return false;
 
     size = record_layout.getSize().getQuantity() * m_ast_context->getCharWidth();
@@ -1685,9 +1672,10 @@ ClangASTSource::layoutRecordType(const RecordDecl *record,
              fi != fe;
              ++fi)
         {
-            log->Printf("LRT[%u]     (FieldDecl*)%p, Name = '%s', Offset = %" PRId64 " bits",
-                        current_id, static_cast<void*>(*fi),
-                        fi->getNameAsString().c_str(), field_offsets[*fi]);
+
+            log->Printf("LRT[%u]     (FieldDecl*)%p, Name = '%s', Offset = %" PRId64 " bits", current_id,
+                        static_cast<void *>(*fi), fi->getNameAsString().c_str(),
+                        record_layout.getFieldOffset(fi->getFieldIndex()));
         }
         DeclFromParser <const CXXRecordDecl> parser_cxx_record = DynCast<const CXXRecordDecl>(parser_record);
         if (parser_cxx_record.IsValid())
@@ -1704,13 +1692,11 @@ ClangASTSource::layoutRecordType(const RecordDecl *record,
                 DeclFromParser <RecordDecl> base_record(base_record_type->getDecl());
                 DeclFromParser <CXXRecordDecl> base_cxx_record = DynCast<CXXRecordDecl>(base_record);
 
-                log->Printf("LRT[%u]     %s(CXXRecordDecl*)%p, Name = '%s', Offset = %" PRId64 " chars",
-                            current_id, (is_virtual ? "Virtual " : ""),
-                            static_cast<void*>(base_cxx_record.decl),
-                            base_cxx_record.decl->getNameAsString().c_str(),
-                            (is_virtual
-                                ? virtual_base_offsets[base_cxx_record.decl].getQuantity()
-                                : base_offsets[base_cxx_record.decl].getQuantity()));
+                clang::CharUnits base_offset = is_virtual ? record_layout.getVBaseClassOffset(base_cxx_record.decl)
+                                                          : record_layout.getBaseClassOffset(base_cxx_record.decl);
+                log->Printf("LRT[%u]     %s(CXXRecordDecl*)%p, Name = '%s', Offset = %" PRId64 " chars", current_id,
+                            (is_virtual ? "Virtual " : ""), static_cast<void *>(base_cxx_record.decl),
+                            base_cxx_record.decl->getNameAsString().c_str(), base_offset);
             }
         }
         else