Page MenuHomePhabricator

[ASTImporter] Limit imports of structs
Needs ReviewPublic

Authored by jarin on Nov 7 2019, 12:08 AM.



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
Breakpoint 1: where = a.out`main + 44 at, 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']

Diff Detail

Event Timeline

jarin created this revision.Nov 7 2019, 12:08 AM
jarin edited the summary of this revision. (Show Details)Nov 7 2019, 12:09 AM
jarin updated this revision to Diff 239235.Jan 21 2020, 12:35 AM

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.

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.

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.

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 "" that is ok. We don't want to copy some definition for "Foo" from "" over into's AST context because if we run again and we get a new we would have to reload 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 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 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, but when we run an expression with this type, we want to be able to have an AST type from with an incomplete definition for "Foo" that we complete during AST import. To do this, we will need to use metadata in the 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)