[lldb-dev] Slow expression evaluation (ASTImporter is too eager?)
Jaroslav Sevcik via lldb-dev
lldb-dev at lists.llvm.org
Thu Nov 14 02:49:36 PST 2019
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
On Thu, Nov 14, 2019 at 11:14 AM Gábor Márton <martongabesz at gmail.com>
wrote:
> 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
>
> On Tue, Nov 12, 2019 at 11:14 AM Jaroslav Sevcik <jarin at google.com> wrote:
>
>>
>> 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
>>>>
>>>>
--
Jaroslav Sevcik | Software Engineer | jarin at google.com |
Google Germany GmbH
Erika-Mann-Str. 33
80636 München
Geschäftsführer: Paul Manicle, Halimah DeLaine Prado | Registergericht und
-nummer: Hamburg, HRB 86891 | Sitz der Gesellschaft: Hamburg
Diese E-Mail ist vertraulich. Wenn Sie nicht der richtige Adressat sind,
leiten Sie diese bitte nicht weiter, informieren Sie den Absender und
löschen Sie die E-Mail und alle Anhänge. Vielen Dank.
This e-mail is confidential. If you are not the right addressee please do
not forward it, please inform the sender, and please erase this e-mail
including any attachments. Thanks.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/lldb-dev/attachments/20191114/87871bcc/attachment-0001.html>
More information about the lldb-dev
mailing list