Slow expression evaluation (ASTImporter is too eager?)

Hello,

I noticed that the AST importer is very eager to import classes/structs that were already completed, 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 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 clang and test performance on several expressions in an Unreal engine sample - preliminary results show this could cut down evaluation time by roughly 50%.

My prototype patch is below; note that couple of lldb tests are failing with a wrong error message, this is a work in progress. What would the experts here think? Is this a plausible direction?

Cheers, Jaro

diff --git a/clang/lib/AST/ASTImporter.cpp b/clang/lib/AST/ASTImporter.cpp

index 54acca7dc62…ebbce5c66c7 100644

— a/clang/lib/AST/ASTImporter.cpp

+++ b/clang/lib/AST/ASTImporter.cpp

@@ -2799,7 +2799,7 @@ ExpectedDecl ASTNodeImporter::VisitRecordDecl(RecordDecl *D) {

if (D->isAnonymousStructOrUnion())

D2->setAnonymousStructOrUnion(true);

  • if (D->isCompleteDefinition())
  • if (!Importer.isMinimalImport() && D->isCompleteDefinition())

if (Error Err = ImportDefinition(D, D2, IDK_Default))

return std::move(Err);

@@ -3438,6 +3438,9 @@ ExpectedDecl ASTNodeImporter::VisitFieldDecl(FieldDecl *D) {

if (ToInitializer)

ToField->setInClassInitializer(ToInitializer);

ToField->setImplicit(D->isImplicit());

  • if (CXXRecordDecl *FieldType = D->getType()->getAsCXXRecordDecl())

  • if (Error Err = ImportDefinitionIfNeeded(FieldType))

  • return std::move(Err);

LexicalDC->addDeclInternal(ToField);

return ToField;

}

@@ -5307,7 +5310,7 @@ ExpectedDecl ASTNodeImporter::VisitClassTemplateSpecializationDecl(

D2->setTemplateSpecializationKind(D->getTemplateSpecializationKind());

  • if (D->isCompleteDefinition())
  • if (!Importer.isMinimalImport() && D->isCompleteDefinition())

if (Error Err = ImportDefinition(D, D2))

return std::move(Err);

—— 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’]

Can you post that patch on Phabricator with an '[ASTImporter]’ as a name prefix? This way the ASTImporter folks will see your patch (The ASTImporter is more of a Clang thing, so they might not read lldb-dev). Also it makes it easier to see/test your patch :slight_smile:

(And +Gabor just in case)

Hi Jaroslav,

Thanks for working on this. Still, there are things that are unclear for me.
I see that LayoutRecordType is called superfluously during the second evaluation of c2.x, ok.

But, could you explain why LLDB is calling that multiple times? Maybe it thinks a type is not completed while it is? As far as I know we keep track which RecordDecl needs completeion in LLDB. At least, we do not store that info in clang::ASTImporter. Minimal import gives a CXXRecordDecl whose DefinitionData is set, even though the members are not imported the definition data is there! So, there is no way for clang::ASTImporter to know which RecordDecl had been imported in a minimal way.

I suspect there are multiple invocations of ASTImporter::ImportDefinition with C2, C1, C0 within ClangASTSource (could you please check that?). And ImportDefinition will blindly import the full definitions recursively even if the minimal import is set (see ASTNodeImporter::IDK_Everything). The patch would change this behavior which I’d like to avoid if possible. I think first we should discover why there are multiple invocations of ASTImporter::ImportDefinition from within LLDB.

Gabor

Hi Gabor,

you are right, there is something funny going on the LLDB side. Let me investigate, I will let you know once I know some more.

Cheers, Jaro

Hi,

thanks for the feedback, I did some more investigation and now I understand
a bit better where the LayoutRecordType calls are coming from. They are initiated by
Clang’s code generation for types, which insists on generating full LLVM types
for any complete RecordDecl (see
https://github.com/llvm-mirror/clang/blob/65acf43270ea2894dffa0d0b292b92402f80c8cb/lib/CodeGen/CodeGenTypes.cpp#L752,
the bailout for incomplete record decls is at
https://github.com/llvm-mirror/clang/blob/master/lib/CodeGen/CodeGenTypes.cpp#L729).
Ideally, clang would only emit forward declarations for any type that is only
used as a pointer, but that is not the case at the moment. It is not quite clear
what else we could do on the lldb side to prevent clang from emitting types for all
those structs. At the end of this email, I am pasting a stack trace that illustrates
the recursive emit for a pointer-chain of structs.

There is also one additional problem with importing base classes. This one is perhaps
more related to AST importer. Again this is best illustrated with an example.

struct F1 { int f1 = 30; };
struct F0 { int f0 = 31; };

struct B0 {
F0 b0f;
};

struct C0 : B0 {
};

struct B1 {
F1 b1f;
int f(C0* c0);
};

struct C1 : B1 {};
struct C2 { int x = 4; C1* c1 = 0; };

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

return 0; // break here
}

If we evaluate c2.x in lldb after evaluating c1 and c0, the AST importer
unnecessarily imports all the classes in this file. The main reason for this is
that the import for structs needs to set the DefaultedDestructorIsConstexpr
bit, which is computed by looking at destructors of base classes. Looking at
the destructors triggers completion and import of the base classes, which in
turn might trigger more imports of base classes. In the example above,
importing C1 will cause completion and import of B1, which in turn causes
import of C0, and recursively completion and import of B0. Below is a
stack trace showing import of field F0::f0 from evaluation of c2.x. The
stack traces going through the
VisitRecordDecl–>ImportDefinition–>setBases path appear to be very hot
in the workloads we see (debugging large codebases). Below is a stack
trace that illustrates visiting F0::f0 from the evaluation of c2.x. The
question is what is the right place to break this long chain of imports.
Ideally, we would not have to import fields of C1 or B1 when evaluating
c2.x. Any ideas?

Stack trace visiting F0::f0 from eval of c2.x, I have tried to highlight
what is imported/completed where.

clang::ASTNodeImporter::VisitFieldDecl ;; Visit F0::f0
clang::declvisitor::Base<…>::Visit
clang::ASTImporter::ImportImpl
lldb_private::ClangASTImporter::ASTImporterDelegate::ImportImpl
clang::ASTImporter::Import
lldb_private::ClangASTImporter::CopyDecl
lldb_private::ClangASTSource::CopyDecl
lldb_private::ClangASTSource::FindExternalLexicalDecls
lldb_private::ClangASTSource::ClangASTSourceProxy::FindExternalLexicalDecls
clang::ExternalASTSource::FindExternalLexicalDecls
clang::DeclContext::LoadLexicalDeclsFromExternalStorage const
clang::DeclContext::buildLookup ;; lookup destructor of B0
clang::DeclContext::lookup const
clang::CXXRecordDecl::getDestructor const
clang::CXXRecordDecl::hasConstexprDestructor const
clang::CXXRecordDecl::addedClassSubobject
clang::CXXRecordDecl::addedMember
clang::DeclContext::addHiddenDecl
clang::DeclContext::addDeclInternal
clang::ASTNodeImporter::VisitFieldDecl ;; visit B0::b0f
clang::declvisitor::Base<…>::Visit
clang::ASTImporter::ImportImpl
lldb_private::ClangASTImporter::ASTImporterDelegate::ImportImpl
clang::ASTImporter::Import
lldb_private::ClangASTImporter::CopyDecl
lldb_private::ClangASTSource::CopyDecl
lldb_private::ClangASTSource::FindExternalLexicalDecls
lldb_private::ClangASTSource::ClangASTSourceProxy::FindExternalLexicalDecls
clang::RecordDecl::LoadFieldsFromExternalStorage const
clang::RecordDecl::field_begin const
clang::RecordDecl::field_empty const ;; fields of B0
clang::CXXRecordDecl::setBases
clang::ASTNodeImporter::ImportDefinition
clang::ASTNodeImporter::VisitRecordDecl ;; visit C0
clang::declvisitor::Base<…>::VisitCXXRecordDecl
clang::declvisitor::Base<…>::Visit
clang::ASTImporter::ImportImpl
lldb_private::ClangASTImporter::ASTImporterDelegate::ImportImpl
clang::ASTImporter::Import
llvm::Expectedclang::RecordDecl* clang::ASTNodeImporter::importclang::RecordDecl
clang::ASTNodeImporter::VisitRecordType
clang::TypeVisitor<clang::ASTNodeImporter, llvm::Expectedclang::QualType >::Visit
clang::ASTImporter::Import
llvm::Expectedclang::QualType clang::ASTNodeImporter::importclang::QualType
clang::ASTNodeImporter::VisitPointerType ;; visit pointer to C0
clang::TypeVisitor<clang::ASTNodeImporter, llvm::Expectedclang::QualType >::Visit
clang::ASTImporter::Import
llvm::Expectedclang::QualType clang::ASTNodeImporter::importclang::QualType
clang::ASTNodeImporter::VisitFunctionProtoType
clang::TypeVisitor<clang::ASTNodeImporter, llvm::Expectedclang::QualType >::Visit
clang::ASTImporter::Import
llvm::Expectedang::QualType clang::ASTNodeImporter::importclang::QualType
llvm::Expected<…> clang::ASTNodeImporter::importSeq<…>
clang::ASTNodeImporter::VisitFunctionDecl
clang::ASTNodeImporter::VisitCXXMethodDecl ;; visit B1::f
clang::declvisitor::Base<…>::Visit
clang::ASTImporter::ImportImpl
lldb_private::ClangASTImporter::ASTImporterDelegate::ImportImpl
clang::ASTImporter::Import
lldb_private::ClangASTImporter::CopyDecl
lldb_private::ClangASTSource::CopyDecl
lldb_private::ClangASTSource::FindExternalLexicalDecls
lldb_private::ClangASTSource::ClangASTSourceProxy::FindExternalLexicalDecls
clang::ExternalASTSource::FindExternalLexicalDecls
clang::DeclContext::LoadLexicalDeclsFromExternalStorage const
clang::DeclContext::buildLookup
clang::DeclContext::lookup const ;; lookup destructor of B1
clang::CXXRecordDecl::getDestructor const
clang::CXXRecordDecl::hasConstexprDestructor const
clang::CXXRecordDecl::addedClassSubobject
clang::CXXRecordDecl::setBases ;; B1
clang::ASTNodeImporter::ImportDefinition
clang::ASTNodeImporter::VisitRecordDecl ;; visit C1
clang::declvisitor::Base<…>::VisitCXXRecordDecl
clang::declvisitor::Base<…>::Visit
clang::ASTImporter::ImportImpl
lldb_private::ClangASTImporter::ASTImporterDelegate::ImportImpl
clang::ASTImporter::Import
llvm::Expectedclang::RecordDecl* clang::ASTNodeImporter::importclang::RecordDecl
clang::ASTNodeImporter::VisitRecordType
clang::TypeVisitor<clang::ASTNodeImporter, llvm::Expectedclang::QualType >::Visit
clang::ASTImporter::Import
llvm::Expectedclang::QualType clang::ASTNodeImporter::importclang::QualType
clang::ASTNodeImporter::VisitPointerType
clang::TypeVisitor<clang::ASTNodeImporter, llvm::Expectedclang::QualType >::Visit
clang::ASTImporter::Import
llvm::Expectedclang::QualType clang::ASTNodeImporter::importclang::QualType
llvm::Expected<…> clang::ASTNodeImporter::importSeq<…>
llvm::Expected<…> clang::ASTNodeImporter::importSeq<…>
clang::ASTNodeImporter::VisitFieldDecl ;; visit C2::c1
clang::declvisitor::Base<…>::Visit
clang::ASTImporter::ImportImpl
lldb_private::ClangASTImporter::ASTImporterDelegate::ImportImpl
clang::ASTImporter::Import
llvm::Expectedclang::Decl* clang::ASTNodeImporter::importclang::Decl
clang::ASTNodeImporter::ImportDeclContext
clang::ASTImporter::ImportDefinition
lldb_private::ClangASTImporter::ASTImporterDelegate::ImportDefinitionTo
lldb_private::ClangASTImporter::CompleteTagDecl
lldb_private::ClangASTSource::CompleteType ;; complete C2
lldb_private::ClangExpressionDeclMap::AddOneVariable
lldb_private::ClangExpressionDeclMap::FindExternalVisibleDecls
lldb_private::ClangExpressionDeclMap::FindExternalVisibleDecls
lldb_private::ClangASTSource::FindExternalVisibleDeclsByName
lldb_private::ClangASTSource::ClangASTSourceProxy::FindExternalVisibleDeclsByName
clang::DeclContext::lookup const
LookupDirect
CppNamespaceLookup
clang::Sema::CppLookupName
clang::Sema::LookupName
clang::Sema::BuildUsingDeclaration

Here is a stack trace that illustrates code gen of types for chain of
references. This was obtain by evaluating c2.x after evaluating c1.x and c0.x
in the following program.

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
}


lldb_private::ClangASTSource::layoutRecordType
lldb_private::ClangASTSource::ClangASTSourceProxy::layoutRecordType
anonymous namespace)::ItaniumRecordLayoutBuilder::InitializeLayout
anonymous namespace)::ItaniumRecordLayoutBuilder::Layout
lang::ASTContext::getASTRecordLayout
anonymous namespace)::CGRecordLowering::CGRecordLowering
anonymous namespace)::CGRecordLowering::CGRecordLowering
lang::CodeGen::CodeGenTypes::ComputeRecordLayout
lang::CodeGen::CodeGenTypes::ConvertRecordDeclType
lang::CodeGen::CodeGenTypes::ConvertType ;; convert C0
clang::CodeGen::CodeGenTypes::ConvertTypeForMem
clang::CodeGen::CodeGenTypes::ConvertType ;; convert ptr to C0
clang::CodeGen::CodeGenTypes::ConvertTypeForMem
(anonymous namespace)::CGRecordLowering::getStorageType
(anonymous namespace)::CGRecordLowering::accumulateFields
(anonymous namespace)::CGRecordLowering::lower
clang::CodeGen::CodeGenTypes::ComputeRecordLayout
clang::CodeGen::CodeGenTypes::ConvertRecordDeclType
clang::CodeGen::CodeGenTypes::ConvertType ;; convert C1
clang::CodeGen::CodeGenTypes::ConvertTypeForMem
clang::CodeGen::CodeGenTypes::ConvertType ;; convert ptr to C1
clang::CodeGen::CodeGenTypes::ConvertTypeForMem
clang::CodeGen::CodeGenModule::GetAddrOfGlobalVar

Hi Jaroslav,

Thank you for digging into this. I think it may be possible to not eagerly import a RecordDecl. Perhaps we could control that from clang::ASTNodeImporter::VisitPointerType and instead of a full import we could just do a minimal import for the PointeeType always. Similarly to references.
But I am not sure about whether we would know during a subsequent import (where the full type is really needed) that the type had been minimally imported before. This requires some more investigation, I’ll come back to you what I find, but it will take some time as this week is quite busy for me.

Gabor

Hi Gabor,

I was thinking about a different idea: perhaps we could try to track on lldb side which recorddecls were requested to be completed during a particular parsing session and only import full definitions if they were requested in this session. If completion was not requested in this session, we would only import forward declaration (even if we already happen to have full definition). Just like you, I have other things to attend to, so it might take some time to prototype that.

I will think about your idea, it is not quite clear to me yet how it solves either of the problems. In the codegen case, it seems to be clang that walks through pointers. In the base class case we already import minimally (I think), but even minimal import causes full import of base classes (perhaps the const destructor check could only import the destructor, though).

Thanks, Jaro

Ok, sounds good.

In the base class case we already import minimally (I think), but even minimal import causes full import
This is deliberate. During construction of ASTImporter the minimal import flag is set. And then when ASTImporter::ImportDefinition is called, it will do a full import, even though minimal import is set. Otherwise we would not be able to get a full type for LLDB.

In the codegen case, it seems to be clang that walks through pointers.
Yes, you are right, my idea probably would not solve that problem. But the base class related problem may be handled with that because the stack trace you sent does include clang::ASTNodeImporter::VisitPointerType. I will elaborate the idea once I found that feasible.

Gabor