[lldb-dev] Slow expression evaluation (ASTImporter is too eager?)
Gábor Márton via lldb-dev
lldb-dev at lists.llvm.org
Thu Nov 14 02:14:14 PST 2019
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
>>>
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/lldb-dev/attachments/20191114/b73a0f93/attachment-0001.html>
More information about the lldb-dev
mailing list