Make the loading of information attached to an IdentifierInfo from an

AST file more lazy, so that we don't eagerly load that information for
all known identifiers each time a new AST file is loaded. The eager
reloading made some sense in the context of precompiled headers, since
very few identifiers were defined before PCH load time. With modules,
however, a huge amount of code can get parsed before we see an
@import, so laziness becomes important here.

The approach taken to make this information lazy is fairly simple:
when we load a new AST file, we mark all of the existing identifiers
as being out-of-date. Whenever we want to access information that may
come from an AST (e.g., whether the identifier has a macro definition,
or what top-level declarations have that name), we check the
out-of-date bit and, if it's set, ask the AST reader to update the
IdentifierInfo from the AST files. The update is a merge, and we now
take care to merge declarations before/after imports with declarations
from multiple imports.

The results of this optimization are fairly dramatic. On a small
application that brings in 14 non-trivial modules, this takes modules
from being > 3x slower than a "perfect" PCH file down to 30% slower
for a full rebuild. A partial rebuild (where the PCH file or modules
can be re-used) is down to 7% slower. Making the PCH file just a
little imperfect (e.g., adding two smallish modules used by a bunch of
.m files that aren't in the PCH file) tips the scales in favor of the
modules approach, with 24% faster partial rebuilds.

This is just a first step; the lazy scheme could possibly be improved
by adding versioning, so we don't search into modules we already
searched. Moreover, we'll need similar lazy schemes for all of the
other lookup data structures, such as DeclContexts.



git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@143100 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 146 insertions, 19 deletions

diff --git a/lib/Sema/IdentifierResolver.cpp b/lib/Sema/IdentifierResolver.cpp
index a643267085..812f5d64fa 100644
--- a/lib/Sema/IdentifierResolver.cpp
+++ b/lib/Sema/IdentifierResolver.cpp
@@ -15,7 +15,10 @@
 #include "clang/Sema/IdentifierResolver.h"
 #include "clang/Sema/Scope.h"
 #include "clang/AST/Decl.h"
+#include "clang/AST/DeclObjC.h"
 #include "clang/Basic/LangOptions.h"
+#include "clang/Lex/ExternalPreprocessorSource.h"
+#include "clang/Lex/Preprocessor.h"
 
 using namespace clang;
 
@@ -93,9 +96,11 @@ IdentifierResolver::IdDeclInfo::ReplaceDecl(NamedDecl *Old, NamedDecl *New) {
 // IdentifierResolver Implementation
 //===----------------------------------------------------------------------===//
 
-IdentifierResolver::IdentifierResolver(const LangOptions &langOpt)
-    : LangOpt(langOpt), IdDeclInfos(new IdDeclInfoMap) {
+IdentifierResolver::IdentifierResolver(Preprocessor &PP)
+  : LangOpt(PP.getLangOptions()), PP(PP),
+    IdDeclInfos(new IdDeclInfoMap) {
 }
+
 IdentifierResolver::~IdentifierResolver() {
   delete IdDeclInfos;
 }
@@ -146,7 +151,7 @@ bool IdentifierResolver::isDeclInScope(Decl *D, DeclContext *Ctx,
 void IdentifierResolver::AddDecl(NamedDecl *D) {
   DeclarationName Name = D->getDeclName();
   if (IdentifierInfo *II = Name.getAsIdentifierInfo())
-    II->setIsFromAST(false);
+    updatingIdentifier(*II);
 
   void *Ptr = Name.getFETokenInfo<void>();
 
@@ -170,6 +175,9 @@ void IdentifierResolver::AddDecl(NamedDecl *D) {
 
 void IdentifierResolver::InsertDeclAfter(iterator Pos, NamedDecl *D) {
   DeclarationName Name = D->getDeclName();
+  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
+    updatingIdentifier(*II);
+  
   void *Ptr = Name.getFETokenInfo<void>();
   
   if (!Ptr) {
@@ -195,7 +203,8 @@ void IdentifierResolver::InsertDeclAfter(iterator Pos, NamedDecl *D) {
   }
 
   if (IdentifierInfo *II = Name.getAsIdentifierInfo())
-    II->setIsFromAST(false);
+    if (II->isFromAST())
+      II->setChangedSinceDeserialization();
   
   // General case: insert the declaration at the appropriate point in the 
   // list, which already has at least two elements.
@@ -212,7 +221,7 @@ void IdentifierResolver::RemoveDecl(NamedDecl *D) {
   assert(D && "null param passed");
   DeclarationName Name = D->getDeclName();
   if (IdentifierInfo *II = Name.getAsIdentifierInfo())
-    II->setIsFromAST(false);
+    updatingIdentifier(*II);
 
   void *Ptr = Name.getFETokenInfo<void>();
 
@@ -233,7 +242,7 @@ bool IdentifierResolver::ReplaceDecl(NamedDecl *Old, NamedDecl *New) {
 
   DeclarationName Name = Old->getDeclName();
   if (IdentifierInfo *II = Name.getAsIdentifierInfo())
-    II->setIsFromAST(false);
+    updatingIdentifier(*II);
 
   void *Ptr = Name.getFETokenInfo<void>();
 
@@ -254,6 +263,9 @@ bool IdentifierResolver::ReplaceDecl(NamedDecl *Old, NamedDecl *New) {
 /// begin - Returns an iterator for decls with name 'Name'.
 IdentifierResolver::iterator
 IdentifierResolver::begin(DeclarationName Name) {
+  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
+    readingIdentifier(*II);
+    
   void *Ptr = Name.getFETokenInfo<void>();
   if (!Ptr) return end();
 
@@ -269,27 +281,142 @@ IdentifierResolver::begin(DeclarationName Name) {
   return end();
 }
 
-void IdentifierResolver::AddDeclToIdentifierChain(IdentifierInfo *II,
-                                                  NamedDecl *D) {
-  II->setIsFromAST(false);
-  void *Ptr = II->getFETokenInfo<void>();
+namespace {
+  enum DeclMatchKind {
+    DMK_Different,
+    DMK_Replace,
+    DMK_Ignore
+  };
+}
 
-  if (!Ptr) {
-    II->setFETokenInfo(D);
-    return;
+/// \brief Compare two declarations to see whether they are different or,
+/// if they are the same, whether the new declaration should replace the 
+/// existing declaration.
+static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New) {
+  // If the declarations are identical, ignore the new one.
+  if (Existing == New)
+    return DMK_Ignore;
+
+  // If the declarations have different kinds, they're obviously different.
+  if (Existing->getKind() != New->getKind())
+    return DMK_Different;
+
+  // If the declarations are redeclarations of each other, keep the newest one.
+  if (Existing->getCanonicalDecl() == New->getCanonicalDecl()) {
+    // If the existing declaration is somewhere in the previous declaration
+    // chain of the new declaration, then prefer the new declaration.
+    for (Decl::redecl_iterator RD = New->redecls_begin(), 
+                            RDEnd = New->redecls_end();
+         RD != RDEnd; ++RD) {
+      if (*RD == Existing)
+        return DMK_Replace;
+        
+      if (RD->isCanonicalDecl())
+        break;
+    }
+    
+    return DMK_Ignore;
   }
+  
+  // If the declarations are both Objective-C classes, and one is a forward
+  // declaration and the other is not, take the full definition.
+  // FIXME: At some point, we'll actually have to detect collisions better.
+  // This logic, however, belongs in the AST reader, not here.
+  if (ObjCInterfaceDecl *ExistingIFace = dyn_cast<ObjCInterfaceDecl>(Existing))
+    if (ObjCInterfaceDecl *NewIFace = dyn_cast<ObjCInterfaceDecl>(New))
+      if (ExistingIFace->isForwardDecl() != NewIFace->isForwardDecl())
+        return ExistingIFace->isForwardDecl()? DMK_Replace : DMK_Ignore;
+        
+  return DMK_Different;
+}
 
+bool IdentifierResolver::tryAddTopLevelDecl(NamedDecl *D, DeclarationName Name){
+  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
+    updatingIdentifier(*II);
+  
+  void *Ptr = Name.getFETokenInfo<void>();
+    
+  if (!Ptr) {
+    Name.setFETokenInfo(D);
+    return true;
+  }
+  
   IdDeclInfo *IDI;
-
+  
   if (isDeclPtr(Ptr)) {
-    II->setFETokenInfo(NULL);
-    IDI = &(*IdDeclInfos)[II];
     NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
-    IDI->AddDecl(PrevD);
-  } else
-    IDI = toIdDeclInfo(Ptr);
+    
+    switch (compareDeclarations(PrevD, D)) {
+    case DMK_Different:
+      break;
+      
+    case DMK_Ignore:
+      return false;
+      
+    case DMK_Replace:
+      Name.setFETokenInfo(D);
+      return true;
+    }
+    
+    Name.setFETokenInfo(NULL);
+    IDI = &(*IdDeclInfos)[Name];
+    
+    // If the existing declaration is not visible in translation unit scope,
+    // then add the new top-level declaration first.
+    if (!PrevD->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
+      IDI->AddDecl(D);
+      IDI->AddDecl(PrevD);
+    } else {
+      IDI->AddDecl(PrevD);
+      IDI->AddDecl(D);
+    }
+    return true;
+  } 
+  
+  IDI = toIdDeclInfo(Ptr);
 
+  // See whether this declaration is identical to any existing declarations.
+  // If not, find the right place to insert it.
+  for (IdDeclInfo::DeclsTy::iterator I = IDI->decls_begin(), 
+                                  IEnd = IDI->decls_end();
+       I != IEnd; ++I) {
+    
+    switch (compareDeclarations(*I, D)) {
+    case DMK_Different:
+      break;
+      
+    case DMK_Ignore:
+      return false;
+      
+    case DMK_Replace:
+      *I = D;
+      return true;
+    }
+    
+    if (!(*I)->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
+      // We've found a declaration that is not visible from the translation
+      // unit (it's in an inner scope). Insert our declaration here.
+      IDI->InsertDecl(I, D);
+      return true;
+    }
+  }
+  
+  // Add the declaration to the end.
   IDI->AddDecl(D);
+  return true;
+}
+
+void IdentifierResolver::readingIdentifier(IdentifierInfo &II) {
+  if (II.isOutOfDate())
+    PP.getExternalSource()->updateOutOfDateIdentifier(II);  
+}
+
+void IdentifierResolver::updatingIdentifier(IdentifierInfo &II) {
+  if (II.isOutOfDate())
+    PP.getExternalSource()->updateOutOfDateIdentifier(II);
+  
+  if (II.isFromAST())
+    II.setChangedSinceDeserialization();
 }
 
 //===----------------------------------------------------------------------===//