[lldb-dev] Slow expression evaluation (ASTImporter is too eager?)
Jaroslav Sevcik via lldb-dev
lldb-dev at lists.llvm.org
Tue Nov 12 02:14:32 PST 2019
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::Expected<clang::RecordDecl*>
clang::ASTNodeImporter::import<clang::RecordDecl>
clang::ASTNodeImporter::VisitRecordType
clang::TypeVisitor<clang::ASTNodeImporter, llvm::Expected<clang::QualType>
>::Visit
clang::ASTImporter::Import
llvm::Expected<clang::QualType>
clang::ASTNodeImporter::import<clang::QualType>
clang::ASTNodeImporter::VisitPointerType ;; visit pointer to C0
clang::TypeVisitor<clang::ASTNodeImporter, llvm::Expected<clang::QualType>
>::Visit
clang::ASTImporter::Import
llvm::Expected<clang::QualType>
clang::ASTNodeImporter::import<clang::QualType>
clang::ASTNodeImporter::VisitFunctionProtoType
clang::TypeVisitor<clang::ASTNodeImporter, llvm::Expected<clang::QualType>
>::Visit
clang::ASTImporter::Import
llvm::Expected<ang::QualType>
clang::ASTNodeImporter::import<clang::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::Expected<clang::RecordDecl*>
clang::ASTNodeImporter::import<clang::RecordDecl>
clang::ASTNodeImporter::VisitRecordType
clang::TypeVisitor<clang::ASTNodeImporter, llvm::Expected<clang::QualType>
>::Visit
clang::ASTImporter::Import
llvm::Expected<clang::QualType>
clang::ASTNodeImporter::import<clang::QualType>
clang::ASTNodeImporter::VisitPointerType
clang::TypeVisitor<clang::ASTNodeImporter, llvm::Expected<clang::QualType>
>::Visit
clang::ASTImporter::Import
llvm::Expected<clang::QualType>
clang::ASTNodeImporter::import<clang::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::Expected<clang::Decl*> clang::ASTNodeImporter::import<clang::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
...
On Fri, Nov 8, 2019 at 9:34 PM Jaroslav Sevcik <jarin at google.com> wrote:
> 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
>
>
>
> On Thu, Nov 7, 2019 at 6:14 PM Gábor Márton <martongabesz at gmail.com>
> wrote:
>
>> 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
>>
>>
>> On Wed, Nov 6, 2019 at 11:21 PM Raphael “Teemperor” Isemann via lldb-dev <
>> lldb-dev at lists.llvm.org> wrote:
>>
>>> 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 :)
>>>
>>> (And +Gabor just in case)
>>>
>>> > On Nov 6, 2019, at 10:25 PM, Jaroslav Sevcik via lldb-dev <
>>> lldb-dev at lists.llvm.org> wrote:
>>> >
>>> > 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']
>>> > ...
>>> >
>>> > _______________________________________________
>>> > lldb-dev mailing list
>>> > lldb-dev at lists.llvm.org
>>> > https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-dev
>>>
>>> _______________________________________________
>>> lldb-dev mailing list
>>> lldb-dev at lists.llvm.org
>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-dev
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/lldb-dev/attachments/20191112/cd893701/attachment-0001.html>
More information about the lldb-dev
mailing list