[ASTImporter] Limit imports of structs

[jarin]

Summary

This is a work in progress patch for discussion. The goal is to improve performance of LLDB's expression evaluator.

During my investigations, I noticed that the AST importer is very eager to import classes/structs that were already completed on the 'From' side, even if they are not needed. This is best illustrated with an example:

struct C0 { int x = 0; };
struct C1 { int x = 1; C0* c0 = 0; };
struct C2 { int x = 2; C1* c1 = 0; };

int main() {
  C0 c0;
  C1 c1;
  C2 c2;

  return 0;  // break here
}

When we evaluate “c2.x” in LLDB, AST importer completes and imports only class C2. This is working as intended. Similarly, evaluating “c1.x” imports just C1 and “c0.x” imports C0. However, if we evaluate “c2.x” after evaluating “c1.x” and “c0.x”, the importer suddenly imports both C1 and C0 (in addition to C2). See a log from a lldb session at the end of this email for illustration.

I believe the culprit here is the following code at the end of the ASTNodeImporter::VisitRecordDecl method:

if (D->isCompleteDefinition())
  if (Error Err = ImportDefinition(D, D2, IDK_Default))
    return std::move(Err);

This will import a definition of a class from LLDB if LLDB already happens to have a complete definition from before. For large programs, this can lead to importing very large chunks of ASTs even if they are not needed. I have tried to remove the code above from the AST importer and test performance on several expressions in an Unreal engine sample - preliminary results show this cuts down evaluation time by roughly 50%.

This is work in progress, couple of lldb tests are failing (but hopefully fixable). What would the experts here think? Is this a plausible direction?

—— lldb session illustrating the unnecessary imports —-
This shows that evaluation of “c2.x” after evaluation “c1.x” and “c0.x” calls to LayoutRecordType for C2, C1 and C0.

$ lldb a.out
(lldb) b h.cc:10
Breakpoint 1: where = a.out`main + 44 at h.cc:10:3, address = ...
(lldb) r
... Process stopped ...
(lldb) log enable lldb expr
(lldb) p c2.x
...
LayoutRecordType[6] ... for (RecordDecl*)0x... [name = 'C2']
...
(lldb) p c1.x
...
LayoutRecordType[7] ... for (RecordDecl*)0x... [name = 'C1']
...
(lldb) p c0.x
...
LayoutRecordType[8] ... for (RecordDecl*)0x... [name = 'C0']
...
(lldb) p c2.x
...
LayoutRecordType[9] ... for (RecordDecl*)0x... [name = 'C2']
LayoutRecordType[10] ... for (RecordDecl*)0x... [name = 'C1']
LayoutRecordType[11] ... for (RecordDecl*)0x... [name = 'C0']
...

[jarin]

I changed the diff so that it does not touch Clang's AST importer, instead it patches LLDB's wrapper of the AST importer.

The idea is to only import complete a record if the current evaluation asked for them to be completed. In particular, if the current evaluation has not ask for a record R to be completed and LLDB is being asked to import R, we supply an incomplete version of R even if we happen to have a complete definition of R lying around in parsed debug info.

This is achieved in a hacky way - if we have a complete record R, we pretend it is incomplete by temporarily clearing R's isCompleteDefinition bit. Interestingly, this hack is already used in ClangASTImporter::ASTImporterDelegate::ImportDefinitionTo.

[teemperor]

I really don't think the ASTImporter should ever manipulate records in the source context (effectively the source context should be considered immutable). It also seems *very* wrong that what we import depends in any way on a previous expression so I agree we should fix that. In theory the ImportDefinition call in the ASTImporter shouldn't do any real work as we have the MinimalImport mode on in LLDB so it should only load some bare bone record with external storage IIUC. So I think the original version of the patch seems like a better approach to me from a quick glance.

In D69933#1830602, @jarin wrote:

This is achieved in a hacky way - if we have a complete record R, we pretend it is incomplete by temporarily clearing R's isCompleteDefinition bit. Interestingly, this hack is already used in ClangASTImporter::ASTImporterDelegate::ImportDefinitionTo.

I don't think we do the same hack in the ClangASTImporter::ASTImporterDelegate::ImportDefinitionTo. There we forcibly set the complete definition bit of the target to the value of the source (and never touch the source AST). But this code also seems really shady as I can't see why we would ever have to do that unless the import goes wrong.

[clayborg]

Clang AST contexts know how to complete types and is done via the external AST source code that will ask a type to complete itself. Each object file has an AST that knows how to lazily complete a type when and only when it is needed. Each object file also only knows about the type information in the binary itself. So if we have a forward declaration to "Foo" with something like "struct Foo;" that is all the object file AST will ever know about this type. This is required because each module can be re-used on subsequent debug sessions if they haven't changed. So if we have a forward declaration for "Foo" in the AST for "bbb.so" that is ok. We don't want to copy some definition for "Foo" from "foo.so" over into bbb.so's AST context because if we run again and we get a new foo.so we would have to reload bbb.so because its copy of "Foo" might be out of date. And we would need to track these interactions.

When we run expressions, we create a new AST and copy types as needed. It would be great if the AST importer only copy over forward declarations of types that can be completed later and can also complete types only as needed when asked.

If I understand correctly that is what this patch is trying to do. Seems like we have a code path that is copying over the type and also completing it sometimes without being asked which should be fixed. If we do fix this, complex expressions become a lot faster. To do this right we should always import forward declarations from the source, and be able to complete the new types in the destination as needed. As teemperor said, the source AST should not be mutated in any way. We should track all of this in the importer and know where we should try to complete the type from.

When using expression AST contexts it is ok to try and import "Foo" from bbb.so since that where is where we first saw the type, and if we aren't successful, we can grab the definition from anywhere else in the debug session. Since each expression has its own AST, it is ok to get the type from anywhere. When searching for this type we should start in the current lldb_private::Block, their pareent blocks, then the file, then the module and then all modules. I think that works today already, but I am not sure if this works for a type "Foo" that is mentioned in a type from a file that doesn't have a complete definition. for example if bbb.so contains:

struct Bar : public Foo {...};

Due to "-flimit-debug-info" the definition for Foo might be forward declared (if the vtable for Foo isn't in the current binary) and not included in this binary. This won't happen on darwin since the default is -fno-limit-debug-info". The DWARF parser knows how to work around this issue when creating the type in the AST for bbb.so, but when we run an expression with this type, we want to be able to have an AST type from bbb.so with an incomplete definition for "Foo" that we complete during AST import. To do this, we will need to use metadata in the bbb.so AST to indicate we have no definition for this type when we normally would require one and be able to complete the type from another source.

So quick things to stick to:

• no modification of the source AST context
• importer can track anything it needs to in order to complete types in complex situations as mentioned above
  • need metadata that tracks types that need to be complete but aren't in the debug info so they can be properly imported for expressions ("struct Bar: public Foo {}", not ok for Foo to not be complete but we allow it for object file AST contexts otherwise clang crashes us)
  • legal forward declarations should be able to be imported as needed even if the AST form the original source doesn't have a complete type ("struct Bar { Foo *foo_ptr; }", ok for Foo to be forward declared here)

lldb/include/lldb/Symbol/ClangASTImporter.h

struct ASTImporterDelegate : public clang::ASTImporter {
     };
 
     void ImportDefinitionTo(clang::Decl *to, clang::Decl *from);
 
     void Imported(clang::Decl *from, clang::Decl *to) override;
 
     clang::Decl *GetOriginalDecl(clang::Decl *To) override;
 
+    void SetCompleted(clang::Decl *from);
+
     void SetImportListener(NewDeclListener *listener) {
       assert(m_new_decl_listener == nullptr && "Already attached a listener?");
       m_new_decl_listener = listener;
     }
     void RemoveImportListener() { m_new_decl_listener = nullptr; }
 
   protected:
     llvm::Expected<clang::Decl *> ImportImpl(clang::Decl *From) override;
 
   private:
     /// Decls we should ignore when mapping decls back to their original
     /// ASTContext. Used by the CxxModuleHandler to mark declarations that
     /// were created from the 'std' C++ module to prevent that the Importer
     /// tries to sync them with the broken equivalent in the debug info AST.
     llvm::SmallPtrSet<clang::Decl *, 16> m_decls_to_ignore;
+    llvm::SmallPtrSet<clang::Decl *, 16> m_completed_decls;
     ClangASTImporter &m_master;
     clang::ASTContext *m_source_ctx;
     CxxModuleHandler *m_std_handler = nullptr;
     /// The currently attached listener.
     NewDeclListener *m_new_decl_listener = nullptr;
   };
 
   typedef std::shared_ptr<ASTImporterDelegate> ImporterDelegateSP;
   typedef llvm::DenseMap<clang::ASTContext *, ImporterDelegateSP> DelegateMap;
   typedef llvm::DenseMap<const clang::NamespaceDecl *, NamespaceMapSP>
       NamespaceMetaMap;
+  typedef std::set<const clang::Decl *> CompletedRecordSet;
 
   struct ASTContextMetadata {
     ASTContextMetadata(clang::ASTContext *dst_ctx)
         : m_dst_ctx(dst_ctx), m_delegates(), m_origins(), m_namespace_maps(),
           m_map_completer(nullptr) {}
 
     clang::ASTContext *m_dst_ctx;
     DelegateMap m_delegates;

lldb/source/Symbol/ClangASTImporter.cpp

CompilerType ClangASTImporter::CopyType(ClangASTContext &dst_ast,
   clang::ASTContext &src_clang_ast = src_ast->getASTContext();
 
   clang::QualType src_qual_type = ClangUtil::GetQualType(src_type);
 
   ImporterDelegateSP delegate_sp(GetDelegate(&dst_clang_ast, &src_clang_ast));
   if (!delegate_sp)
     return CompilerType();
 
+  delegate_sp->SetCompleted(src_qual_type->getAsTagDecl());
+
   ASTImporterDelegate::CxxModuleScope std_scope(*delegate_sp, &dst_clang_ast);
 
   llvm::Expected<QualType> ret_or_error = delegate_sp->Import(src_qual_type);
+
   if (!ret_or_error) {
     Log *log =
       lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_EXPRESSIONS);
     LLDB_LOG_ERROR(log, ret_or_error.takeError(),
         "Couldn't import type: {0}");
     return CompilerType();
   }
 
while (!m_decls_to_complete.empty()) {
 
       Decl *original_decl = to_context_md->m_origins[decl].decl;
 
       // Complete the decl now.
       ClangASTContext::GetCompleteDecl(m_src_ctx, original_decl);
       if (auto *tag_decl = dyn_cast<TagDecl>(decl)) {
         if (auto *original_tag_decl = dyn_cast<TagDecl>(original_decl)) {
           if (original_tag_decl->isCompleteDefinition()) {
+            m_delegate->SetCompleted(original_tag_decl);
             m_delegate->ImportDefinitionTo(tag_decl, original_tag_decl);
             tag_decl->setCompleteDefinition(true);
           }
         }
 
         tag_decl->setHasExternalLexicalStorage(false);
         tag_decl->setHasExternalVisibleStorage(false);
       } else if (auto *container_decl = dyn_cast<ObjCContainerDecl>(decl)) {
if (!decl_origin.Valid())
     return false;
 
   if (!ClangASTContext::GetCompleteDecl(decl_origin.ctx, decl_origin.decl))
     return false;
 
   ImporterDelegateSP delegate_sp(
       GetDelegate(&decl->getASTContext(), decl_origin.ctx));
 
+  delegate_sp->SetCompleted(decl_origin.decl);
+
   ASTImporterDelegate::CxxModuleScope std_scope(*delegate_sp,
                                                 &decl->getASTContext());
   if (delegate_sp)
     delegate_sp->ImportDefinitionTo(decl, decl_origin.decl);
 
   return true;
 }
 
if (iter->second.ctx == src_ast)
       md->m_origins.erase(iter++);
     else
       ++iter;
   }
 }
 
 ClangASTImporter::MapCompleter::~MapCompleter() { return; }
 
+void ClangASTImporter::ASTImporterDelegate::SetCompleted(Decl *from) {
+  m_completed_decls.insert(from);
+}
+
 llvm::Expected<Decl *>
 ClangASTImporter::ASTImporterDelegate::ImportImpl(Decl *From) {
   if (m_std_handler) {
     llvm::Optional<Decl *> D = m_std_handler->Import(From);
     if (D) {
       // Make sure we don't use this decl later to map it back to it's original
       // decl. The decl the CxxModuleHandler created has nothing to do with
       // the one from debug info, and linking those two would just cause the
ClangASTImporter::ASTImporterDelegate::ImportImpl(Decl *From) {
   if (origin.Valid()) {
     auto R = m_master.CopyDecl(&getToContext(), origin.decl);
     if (R) {
       RegisterImportedDecl(From, R);
       return R;
     }
   }
 
-  return ASTImporter::ImportImpl(From);
+  CXXRecordDecl *record_decl_to_set_complete = nullptr;
+  if (CXXRecordDecl *record_decl = dyn_cast<CXXRecordDecl>(From)) {
+    if (record_decl->isCompleteDefinition() &&
+        !record_decl->isAnonymousStructOrUnion() &&
+        m_completed_decls.find(From) == m_completed_decls.end()) {
+      record_decl->setCompleteDefinition(false);
+      record_decl_to_set_complete = record_decl;
+    }
+  }
+  llvm::Expected<Decl *> result = ASTImporter::ImportImpl(From);
+  if (record_decl_to_set_complete) {
+    record_decl_to_set_complete->setCompleteDefinition(true);
+  }
+  return result;
 }
 
 void ClangASTImporter::ASTImporterDelegate::ImportDefinitionTo(
     clang::Decl *to, clang::Decl *from) {
   ASTImporter::Imported(from, to);
 
   /*
   if (to_objc_interface)