Use the AST on-disk hash table for name lookup inside a DeclContext.

*Huge* improvement over the amount of deserializing that we do for C++ lookup.
e.g, if he have the Carbon header precompiled and include it on a file containing this:

int x;

these are the before/after stats:

BEFORE:

*** AST File Statistics:
  578 stat cache hits
  4 stat cache misses
  548/30654 source location entries read (1.787695%)
  15907/16501 types read (96.400223%)
  53525/59955 declarations read (89.275291%)
  33993/43525 identifiers read (78.099945%)
  41516/51891 statements read (80.006165%)
  77/5317 macros read (1.448185%)
  0/6335 lexical declcontexts read (0.000000%)
  1/5424 visible declcontexts read (0.018437%)

AFTER using the on-disk table:

*** AST File Statistics:
  578 stat cache hits
  4 stat cache misses
  548/30654 source location entries read (1.787695%)
  10/16501 types read (0.060602%)
  9/59955 declarations read (0.015011%)
  161/43525 identifiers read (0.369902%)
  20/51891 statements read (0.038542%)
  6/5317 macros read (0.112846%)
  0/6335 lexical declcontexts read (0.000000%)
  2/5424 visible declcontexts read (0.036873%)

There's only one issue affecting mostly the precompiled preambles which I will address soon.

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

9 files changed, 198 insertions, 354 deletions

diff --git a/include/clang/AST/DeclContextInternals.h b/include/clang/AST/DeclContextInternals.h
index 9602b677fc..97da6ca9a1 100644
--- a/include/clang/AST/DeclContextInternals.h
+++ b/include/clang/AST/DeclContextInternals.h
@@ -29,108 +29,54 @@ class DependentDiagnostic;
 /// StoredDeclsList - This is an array of decls optimized a common case of only
 /// containing one entry.
 struct StoredDeclsList {
-  /// The kind of data encoded in this list.
-  enum DataKind {
-    /// \brief The data is a NamedDecl*.
-    DK_Decl = 0,
-    /// \brief The data is a declaration ID (an unsigned value),
-    /// shifted left by 2 bits.
-    DK_DeclID = 1,
-    /// \brief The data is a pointer to a vector (of type VectorTy)
-    /// that contains declarations.
-    DK_Decl_Vector = 2,
-    /// \brief The data is a pointer to a vector (of type VectorTy)
-    /// that contains declaration ID.
-    DK_ID_Vector = 3
-  };
-
-  /// VectorTy - When in vector form, this is what the Data pointer points to.
-  typedef llvm::SmallVector<uintptr_t, 4> VectorTy;
-
-  /// \brief The stored data, which will be either a declaration ID, a
-  /// pointer to a NamedDecl, or a pointer to a vector.
-  uintptr_t Data;
+
+  /// DeclsTy - When in vector form, this is what the Data pointer points to.
+  typedef llvm::SmallVector<NamedDecl *, 4> DeclsTy;
+
+  /// \brief The stored data, which will be either a pointer to a NamedDecl,
+  /// or a pointer to a vector.
+  llvm::PointerUnion<NamedDecl *, DeclsTy *> Data;
 
 public:
-  StoredDeclsList() : Data(0) {}
+  StoredDeclsList() {}
 
   StoredDeclsList(const StoredDeclsList &RHS) : Data(RHS.Data) {
-    if (VectorTy *RHSVec = RHS.getAsVector()) {
-      VectorTy *New = new VectorTy(*RHSVec);
-      Data = reinterpret_cast<uintptr_t>(New) | (Data & 0x03);
-    }
+    if (DeclsTy *RHSVec = RHS.getAsVector())
+      Data = new DeclsTy(*RHSVec);
   }
 
   ~StoredDeclsList() {
     // If this is a vector-form, free the vector.
-    if (VectorTy *Vector = getAsVector())
+    if (DeclsTy *Vector = getAsVector())
       delete Vector;
   }
 
   StoredDeclsList &operator=(const StoredDeclsList &RHS) {
-    if (VectorTy *Vector = getAsVector())
+    if (DeclsTy *Vector = getAsVector())
       delete Vector;
     Data = RHS.Data;
-    if (VectorTy *RHSVec = RHS.getAsVector()) {
-      VectorTy *New = new VectorTy(*RHSVec);
-      Data = reinterpret_cast<uintptr_t>(New) | (Data & 0x03);
-    }
+    if (DeclsTy *RHSVec = RHS.getAsVector())
+      Data = new DeclsTy(*RHSVec);
     return *this;
   }
 
-  bool isNull() const { return (Data & ~0x03) == 0; }
+  bool isNull() const { return Data.isNull(); }
 
   NamedDecl *getAsDecl() const {
-    if ((Data & 0x03) != DK_Decl)
-      return 0;
-
-    return reinterpret_cast<NamedDecl *>(Data & ~0x03);
+    return Data.dyn_cast<NamedDecl *>();
   }
 
-  VectorTy *getAsVector() const {
-    if ((Data & 0x03) != DK_ID_Vector && (Data & 0x03) != DK_Decl_Vector)
-      return 0;
-
-    return reinterpret_cast<VectorTy *>(Data & ~0x03);
+  DeclsTy *getAsVector() const {
+    return Data.dyn_cast<DeclsTy *>();
   }
 
   void setOnlyValue(NamedDecl *ND) {
     assert(!getAsVector() && "Not inline");
-    Data = reinterpret_cast<uintptr_t>(ND);
-  }
-
-  void setFromDeclIDs(const llvm::SmallVectorImpl<unsigned> &Vec) {
-    if (Vec.size() > 1) {
-      VectorTy *Vector = getAsVector();
-      if (!Vector) {
-        Vector = new VectorTy;
-        Data = reinterpret_cast<uintptr_t>(Vector) | DK_ID_Vector;
-      }
-
-      Vector->resize(Vec.size());
-      std::copy(Vec.begin(), Vec.end(), Vector->begin());
-      return;
-    }
-
-    if (VectorTy *Vector = getAsVector())
-      delete Vector;
-
-    if (Vec.empty())
-      Data = 0;
-    else
-      Data = (Vec[0] << 2) | DK_DeclID;
-  }
-
-  /// \brief Force the stored declarations list to contain actual
-  /// declarations.
-  ///
-  /// This routine will resolve any declaration IDs for declarations
-  /// that may not yet have been loaded from external storage.
-  void materializeDecls(ASTContext &Context);
-
-  bool hasDeclarationIDs() const {
-    DataKind DK = (DataKind)(Data & 0x03);
-    return DK == DK_DeclID || DK == DK_ID_Vector;
+    Data = ND;
+    // Make sure that Data is a plain NamedDecl* so we can use its address
+    // at getLookupResult.
+    assert(*(NamedDecl **)&Data == ND &&
+           "PointerUnion mangles the NamedDecl pointer!");
   }
 
   void remove(NamedDecl *D) {
@@ -138,30 +84,26 @@ public:
     if (NamedDecl *Singleton = getAsDecl()) {
       assert(Singleton == D && "list is different singleton");
       (void)Singleton;
-      Data = 0;
+      Data = (NamedDecl *)0;
       return;
     }
 
-    VectorTy &Vec = *getAsVector();
-    VectorTy::iterator I = std::find(Vec.begin(), Vec.end(),
-                                     reinterpret_cast<uintptr_t>(D));
+    DeclsTy &Vec = *getAsVector();
+    DeclsTy::iterator I = std::find(Vec.begin(), Vec.end(), D);
     assert(I != Vec.end() && "list does not contain decl");
     Vec.erase(I);
 
-    assert(std::find(Vec.begin(), Vec.end(), reinterpret_cast<uintptr_t>(D))
+    assert(std::find(Vec.begin(), Vec.end(), D)
              == Vec.end() && "list still contains decl");
   }
 
   /// getLookupResult - Return an array of all the decls that this list
   /// represents.
-  DeclContext::lookup_result getLookupResult(ASTContext &Context) {
+  DeclContext::lookup_result getLookupResult() {
     if (isNull())
       return DeclContext::lookup_result(DeclContext::lookup_iterator(0),
                                         DeclContext::lookup_iterator(0));
 
-    if (hasDeclarationIDs())
-      materializeDecls(Context);
-
     // If we have a single NamedDecl, return it.
     if (getAsDecl()) {
       assert(!isNull() && "Empty list isn't allowed");
@@ -172,19 +114,15 @@ public:
     }
 
     assert(getAsVector() && "Must have a vector at this point");
-    VectorTy &Vector = *getAsVector();
+    DeclsTy &Vector = *getAsVector();
 
     // Otherwise, we have a range result.
-    return DeclContext::lookup_result((NamedDecl **)&Vector[0],
-                                      (NamedDecl **)&Vector[0]+Vector.size());
+    return DeclContext::lookup_result(&Vector[0], &Vector[0]+Vector.size());
   }
 
   /// HandleRedeclaration - If this is a redeclaration of an existing decl,
   /// replace the old one with D and return true.  Otherwise return false.
-  bool HandleRedeclaration(ASTContext &Context, NamedDecl *D) {
-    if (hasDeclarationIDs())
-      materializeDecls(Context);
-
+  bool HandleRedeclaration(NamedDecl *D) {
     // Most decls only have one entry in their list, special case it.
     if (NamedDecl *OldD = getAsDecl()) {
       if (!D->declarationReplaces(OldD))
@@ -194,12 +132,12 @@ public:
     }
 
     // Determine if this declaration is actually a redeclaration.
-    VectorTy &Vec = *getAsVector();
-    for (VectorTy::iterator OD = Vec.begin(), ODEnd = Vec.end();
+    DeclsTy &Vec = *getAsVector();
+    for (DeclsTy::iterator OD = Vec.begin(), ODEnd = Vec.end();
          OD != ODEnd; ++OD) {
-      NamedDecl *OldD = reinterpret_cast<NamedDecl *>(*OD);
+      NamedDecl *OldD = *OD;
       if (D->declarationReplaces(OldD)) {
-        *OD = reinterpret_cast<uintptr_t>(D);
+        *OD = D;
         return true;
       }
     }
@@ -211,17 +149,15 @@ public:
   /// not a redeclaration to merge it into the appropriate place in our list.
   ///
   void AddSubsequentDecl(NamedDecl *D) {
-    assert(!hasDeclarationIDs() && "Must materialize before adding decls");
-
     // If this is the second decl added to the list, convert this to vector
     // form.
     if (NamedDecl *OldD = getAsDecl()) {
-      VectorTy *VT = new VectorTy();
-      VT->push_back(reinterpret_cast<uintptr_t>(OldD));
-      Data = reinterpret_cast<uintptr_t>(VT) | DK_Decl_Vector;
+      DeclsTy *VT = new DeclsTy();
+      VT->push_back(OldD);
+      Data = VT;
     }
 
-    VectorTy &Vec = *getAsVector();
+    DeclsTy &Vec = *getAsVector();
 
     // Using directives end up in a special entry which contains only
     // other using directives, so all this logic is wasted for them.
@@ -232,32 +168,30 @@ public:
     // iterator which points at the first tag will start a span of
     // decls that only contains tags.
     if (D->hasTagIdentifierNamespace())
-      Vec.push_back(reinterpret_cast<uintptr_t>(D));
+      Vec.push_back(D);
 
     // Resolved using declarations go at the front of the list so that
     // they won't show up in other lookup results.  Unresolved using
     // declarations (which are always in IDNS_Using | IDNS_Ordinary)
     // follow that so that the using declarations will be contiguous.
     else if (D->getIdentifierNamespace() & Decl::IDNS_Using) {
-      VectorTy::iterator I = Vec.begin();
+      DeclsTy::iterator I = Vec.begin();
       if (D->getIdentifierNamespace() != Decl::IDNS_Using) {
         while (I != Vec.end() &&
-               reinterpret_cast<NamedDecl *>(*I)
-                 ->getIdentifierNamespace() == Decl::IDNS_Using)
+               (*I)->getIdentifierNamespace() == Decl::IDNS_Using)
           ++I;
       }
-      Vec.insert(I, reinterpret_cast<uintptr_t>(D));
+      Vec.insert(I, D);
 
     // All other declarations go at the end of the list, but before any
     // tag declarations.  But we can be clever about tag declarations
     // because there can only ever be one in a scope.
-    } else if (reinterpret_cast<NamedDecl *>(Vec.back())
-                 ->hasTagIdentifierNamespace()) {
-      uintptr_t TagD = Vec.back();
-      Vec.back() = reinterpret_cast<uintptr_t>(D);
+    } else if (Vec.back()->hasTagIdentifierNamespace()) {
+      NamedDecl *TagD = Vec.back();
+      Vec.back() = D;
       Vec.push_back(TagD);
     } else
-      Vec.push_back(reinterpret_cast<uintptr_t>(D));
+      Vec.push_back(D);
   }
 };
 
diff --git a/include/clang/AST/ExternalASTSource.h b/include/clang/AST/ExternalASTSource.h
index d23e75dd38..24d9bc5bca 100644
--- a/include/clang/AST/ExternalASTSource.h
+++ b/include/clang/AST/ExternalASTSource.h
@@ -27,18 +27,6 @@ class DeclContext;
 class ExternalSemaSource; // layering violation required for downcasting
 class Stmt;
 
-/// \brief The deserialized representation of a set of declarations
-/// with the same name that are visible in a given context.
-struct VisibleDeclaration {
-  /// \brief The name of the declarations.
-  DeclarationName Name;
-
-  /// \brief The ID numbers of all of the declarations with this name.
-  ///
-  /// These declarations have not necessarily been de-serialized.
-  llvm::SmallVector<unsigned, 4> Declarations;
-};
-
 /// \brief Abstract interface for external sources of AST nodes.
 ///
 /// External AST sources provide AST nodes constructed from some
@@ -140,22 +128,6 @@ public:
   virtual void PrintStats();
 
 protected:
-  /// \brief Initialize the context's lookup map with the given decls.
-  /// It is assumed that none of the declarations are redeclarations of
-  /// each other.
-  static void SetExternalVisibleDecls(const DeclContext *DC,
-                  const llvm::SmallVectorImpl<VisibleDeclaration> &Decls);
-
-  /// \brief Initialize the context's lookup map with the given decls.
-  /// It is assumed that none of the declarations are redeclarations of
-  /// each other.
-  static void SetExternalVisibleDecls(const DeclContext *DC,
-                              const llvm::SmallVectorImpl<NamedDecl*> &Decls);
-
-  static DeclContext::lookup_result
-  SetExternalVisibleDeclsForName(const DeclContext *DC,
-                                 const VisibleDeclaration &VD);
-
   static DeclContext::lookup_result
   SetExternalVisibleDeclsForName(const DeclContext *DC,
                                  DeclarationName Name,
diff --git a/include/clang/Serialization/ASTReader.h b/include/clang/Serialization/ASTReader.h
index aff52195a9..3f7480cee7 100644
--- a/include/clang/Serialization/ASTReader.h
+++ b/include/clang/Serialization/ASTReader.h
@@ -339,8 +339,7 @@ private:
 
   /// \brief Information about the contents of a DeclContext.
   struct DeclContextInfo {
-    llvm::BitstreamCursor *Stream;
-    uint64_t OffsetToVisibleDecls;
+    void *NameLookupTableData; // a ASTDeclContextNameLookupTable.
     const serialization::DeclID *LexicalDecls;
     unsigned NumLexicalDecls;
   };
diff --git a/include/clang/Serialization/ASTWriter.h b/include/clang/Serialization/ASTWriter.h
index 9ef14925bc..75216bf8be 100644
--- a/include/clang/Serialization/ASTWriter.h
+++ b/include/clang/Serialization/ASTWriter.h
@@ -268,6 +268,7 @@ private:
 
   unsigned ParmVarDeclAbbrev;
   unsigned DeclContextLexicalAbbrev;
+  unsigned DeclContextVisibleLookupAbbrev;
   void WriteDeclsBlockAbbrevs();
   void WriteDecl(ASTContext &Context, Decl *D);
 
diff --git a/lib/AST/DeclBase.cpp b/lib/AST/DeclBase.cpp
index 74cc1c29b9..30d540a00a 100644
--- a/lib/AST/DeclBase.cpp
+++ b/lib/AST/DeclBase.cpp
@@ -648,19 +648,6 @@ ExternalASTSource::SetNoExternalVisibleDeclsForName(const DeclContext *DC,
 
 DeclContext::lookup_result
 ExternalASTSource::SetExternalVisibleDeclsForName(const DeclContext *DC,
-                                          const VisibleDeclaration &VD) {
-  ASTContext &Context = DC->getParentASTContext();
-  StoredDeclsMap *Map;
-  if (!(Map = DC->LookupPtr))
-    Map = DC->CreateStoredDeclsMap(Context);
-
-  StoredDeclsList &List = (*Map)[VD.Name];
-  List.setFromDeclIDs(VD.Declarations);
-  return List.getLookupResult(Context);
-}
-
-DeclContext::lookup_result
-ExternalASTSource::SetExternalVisibleDeclsForName(const DeclContext *DC,
                                                   DeclarationName Name,
                                     llvm::SmallVectorImpl<NamedDecl*> &Decls) {
   ASTContext &Context = DC->getParentASTContext();;
@@ -677,35 +664,7 @@ ExternalASTSource::SetExternalVisibleDeclsForName(const DeclContext *DC,
       List.AddSubsequentDecl(Decls[I]);
   }
 
-  return List.getLookupResult(Context);
-}
-
-void ExternalASTSource::SetExternalVisibleDecls(const DeclContext *DC,
-                    const llvm::SmallVectorImpl<VisibleDeclaration> &Decls) {
-  // There is no longer any visible storage in this context.
-  DC->ExternalVisibleStorage = false;
-
-  assert(!DC->LookupPtr && "Have a lookup map before de-serialization?");
-  StoredDeclsMap *Map = DC->CreateStoredDeclsMap(DC->getParentASTContext());
-  for (unsigned I = 0, N = Decls.size(); I != N; ++I) {
-    (*Map)[Decls[I].Name].setFromDeclIDs(Decls[I].Declarations);
-  }
-}
-
-void ExternalASTSource::SetExternalVisibleDecls(const DeclContext *DC,
-                            const llvm::SmallVectorImpl<NamedDecl*> &Decls) {
-  // There is no longer any visible storage in this context.
-  DC->ExternalVisibleStorage = false;
-
-  assert(!DC->LookupPtr && "Have a lookup map before de-serialization?");
-  StoredDeclsMap &Map = *DC->CreateStoredDeclsMap(DC->getParentASTContext());
-  for (unsigned I = 0, N = Decls.size(); I != N; ++I) {
-    StoredDeclsList &List = Map[Decls[I]->getDeclName()];
-    if (List.isNull())
-      List.setOnlyValue(Decls[I]);
-    else
-      List.AddSubsequentDecl(Decls[I]);
-  }
+  return List.getLookupResult();
 }
 
 DeclContext::decl_iterator DeclContext::noload_decls_begin() const {
@@ -841,7 +800,7 @@ DeclContext::lookup(DeclarationName Name) {
     if (LookupPtr) {
       StoredDeclsMap::iterator I = LookupPtr->find(Name);
       if (I != LookupPtr->end())
-        return I->second.getLookupResult(getParentASTContext());
+        return I->second.getLookupResult();
     }
 
     ExternalASTSource *Source = getParentASTContext().getExternalSource();
@@ -861,7 +820,7 @@ DeclContext::lookup(DeclarationName Name) {
   StoredDeclsMap::iterator Pos = LookupPtr->find(Name);
   if (Pos == LookupPtr->end())
     return lookup_result(lookup_iterator(0), lookup_iterator(0));
-  return Pos->second.getLookupResult(getParentASTContext());
+  return Pos->second.getLookupResult();
 }
 
 DeclContext::lookup_const_result
@@ -925,18 +884,21 @@ void DeclContext::makeDeclVisibleInContextImpl(NamedDecl *D) {
   if (isa<ClassTemplateSpecializationDecl>(D))
     return;
 
-  // If there is an external AST source, load any declarations it knows about
-  // with this declaration's name.
-  if (ExternalASTSource *Source = getParentASTContext().getExternalSource())
-    if (hasExternalVisibleStorage())
-      Source->FindExternalVisibleDeclsByName(this, D->getDeclName());
-
   ASTContext *C = 0;
   if (!LookupPtr) {
     C = &getParentASTContext();
     CreateStoredDeclsMap(*C);
   }
 
+  // If there is an external AST source, load any declarations it knows about
+  // with this declaration's name.
+  // If the lookup table contains an entry about this name it means that we
+  // have already checked the external source.
+  if (ExternalASTSource *Source = getParentASTContext().getExternalSource())
+    if (hasExternalVisibleStorage() &&
+        LookupPtr->find(D->getDeclName()) == LookupPtr->end())
+      Source->FindExternalVisibleDeclsByName(this, D->getDeclName());
+
   // Insert this declaration into the map.
   StoredDeclsList &DeclNameEntries = (*LookupPtr)[D->getDeclName()];
   if (DeclNameEntries.isNull()) {
@@ -947,10 +909,7 @@ void DeclContext::makeDeclVisibleInContextImpl(NamedDecl *D) {
   // If it is possible that this is a redeclaration, check to see if there is
   // already a decl for which declarationReplaces returns true.  If there is
   // one, just replace it and return.
-  if (!C)
-    C = &getParentASTContext();
-  
-  if (DeclNameEntries.HandleRedeclaration(*C, D))
+  if (DeclNameEntries.HandleRedeclaration(D))
     return;
 
   // Put this declaration into the appropriate slot.
@@ -966,43 +925,6 @@ DeclContext::getUsingDirectives() const {
                              reinterpret_cast<udir_iterator>(Result.second));
 }
 
-void StoredDeclsList::materializeDecls(ASTContext &Context) {
-  if (isNull())
-    return;
-
-  switch ((DataKind)(Data & 0x03)) {
-  case DK_Decl:
-  case DK_Decl_Vector:
-    break;
-
-  case DK_DeclID: {
-    // Resolve this declaration ID to an actual declaration by
-    // querying the external AST source.
-    unsigned DeclID = Data >> 2;
-
-    ExternalASTSource *Source = Context.getExternalSource();
-    assert(Source && "No external AST source available!");
-
-    Data = reinterpret_cast<uintptr_t>(Source->GetExternalDecl(DeclID));
-    break;
-  }
-
-  case DK_ID_Vector: {
-    // We have a vector of declaration IDs. Resolve all of them to
-    // actual declarations.
-    VectorTy &Vector = *getAsVector();
-    ExternalASTSource *Source = Context.getExternalSource();
-    assert(Source && "No external AST source available!");
-
-    for (unsigned I = 0, N = Vector.size(); I != N; ++I)
-      Vector[I] = reinterpret_cast<uintptr_t>(Source->GetExternalDecl(Vector[I]));
-
-    Data = (Data & ~0x03) | DK_Decl_Vector;
-    break;
-  }
-  }
-}
-
 //===----------------------------------------------------------------------===//
 // Creation and Destruction of StoredDeclsMaps.                               //
 //===----------------------------------------------------------------------===//
diff --git a/lib/Serialization/ASTReader.cpp b/lib/Serialization/ASTReader.cpp
index 05fa7cd115..b24b35309a 100644
--- a/lib/Serialization/ASTReader.cpp
+++ b/lib/Serialization/ASTReader.cpp
@@ -846,6 +846,54 @@ public:
 typedef OnDiskChainedHashTable<ASTDeclContextNameLookupTrait>
   ASTDeclContextNameLookupTable;
 
+bool ASTReader::ReadDeclContextStorage(llvm::BitstreamCursor &Cursor,
+                                   const std::pair<uint64_t, uint64_t> &Offsets,
+                                       DeclContextInfo &Info) {
+  SavedStreamPosition SavedPosition(Cursor);
+  // First the lexical decls.
+  if (Offsets.first != 0) {
+    Cursor.JumpToBit(Offsets.first);
+
+    RecordData Record;
+    const char *Blob;
+    unsigned BlobLen;
+    unsigned Code = Cursor.ReadCode();
+    unsigned RecCode = Cursor.ReadRecord(Code, Record, &Blob, &BlobLen);
+    if (RecCode != DECL_CONTEXT_LEXICAL) {
+      Error("Expected lexical block");
+      return true;
+    }
+
+    Info.LexicalDecls = reinterpret_cast<const DeclID*>(Blob);
+    Info.NumLexicalDecls = BlobLen / sizeof(DeclID);
+  } else {
+    Info.LexicalDecls = 0;
+    Info.NumLexicalDecls = 0;
+  }
+
+  // Now the lookup table.
+  if (Offsets.second != 0) {
+    Cursor.JumpToBit(Offsets.second);
+
+    RecordData Record;
+    const char *Blob;
+    unsigned BlobLen;
+    unsigned Code = Cursor.ReadCode();
+    unsigned RecCode = Cursor.ReadRecord(Code, Record, &Blob, &BlobLen);
+    if (RecCode != DECL_CONTEXT_VISIBLE) {
+      Error("Expected visible lookup table block");
+      return true;
+    }
+    Info.NameLookupTableData
+      = ASTDeclContextNameLookupTable::Create(
+                    (const unsigned char *)Blob + Record[0],
+                    (const unsigned char *)Blob,
+                    ASTDeclContextNameLookupTrait(*this));
+  }
+
+  return false;
+}
+
 void ASTReader::Error(const char *Msg) {
   Diag(diag::err_fe_pch_malformed) << Msg;
 }
@@ -1674,7 +1722,7 @@ ASTReader::ReadASTBlock(PerFileData &F) {
 
     case TU_UPDATE_LEXICAL: {
       DeclContextInfo Info = {
-        /* No visible information */ 0, 0,
+        /* No visible information */ 0,
         reinterpret_cast<const DeclID *>(BlobStart),
         BlobLen / sizeof(DeclID)
       };
@@ -3119,54 +3167,33 @@ ASTReader::FindExternalVisibleDeclsByName(const DeclContext *DC,
                                           DeclarationName Name) {
   assert(DC->hasExternalVisibleStorage() &&
          "DeclContext has no visible decls in storage");
+  if (!Name)
+    return DeclContext::lookup_result(DeclContext::lookup_iterator(0),
+                                      DeclContext::lookup_iterator(0));
 
-  llvm::SmallVector<VisibleDeclaration, 64> Decls;
+  llvm::SmallVector<NamedDecl *, 64> Decls;
   // There might be lexical decls in multiple parts of the chain, for the TU
   // and namespaces.
   DeclContextInfos &Infos = DeclContextOffsets[DC];
   for (DeclContextInfos::iterator I = Infos.begin(), E = Infos.end();
        I != E; ++I) {
-    uint64_t Offset = I->OffsetToVisibleDecls;
-    if (Offset == 0)
+    if (!I->NameLookupTableData)
       continue;
 
-    llvm::BitstreamCursor &DeclsCursor = *I->Stream;
-
-    // Keep track of where we are in the stream, then jump back there
-    // after reading this context.
-    SavedStreamPosition SavedPosition(DeclsCursor);
-
-    // Load the record containing all of the declarations visible in
-    // this context.
-    DeclsCursor.JumpToBit(Offset);
-    RecordData Record;
-    unsigned Code = DeclsCursor.ReadCode();
-    unsigned RecCode = DeclsCursor.ReadRecord(Code, Record);
-    if (RecCode != DECL_CONTEXT_VISIBLE) {
-      Error("Expected visible block");
-      return DeclContext::lookup_result(DeclContext::lookup_iterator(),
-                                        DeclContext::lookup_iterator());
-    }
-
-    if (Record.empty())
+    ASTDeclContextNameLookupTable *LookupTable =
+        (ASTDeclContextNameLookupTable*)I->NameLookupTableData;
+    ASTDeclContextNameLookupTable::iterator Pos = LookupTable->find(Name);
+    if (Pos == LookupTable->end())
       continue;
 
-    unsigned Idx = 0;
-    while (Idx < Record.size()) {
-      Decls.push_back(VisibleDeclaration());
-      Decls.back().Name = ReadDeclarationName(Record, Idx);
-
-      unsigned Size = Record[Idx++];
-      llvm::SmallVector<unsigned, 4> &LoadedDecls = Decls.back().Declarations;
-      LoadedDecls.reserve(Size);
-      for (unsigned J = 0; J < Size; ++J)
-        LoadedDecls.push_back(Record[Idx++]);
-    }
+    ASTDeclContextNameLookupTrait::data_type Data = *Pos;
+    for (; Data.first != Data.second; ++Data.first)
+      Decls.push_back(cast<NamedDecl>(GetDecl(*Data.first)));
   }
 
   ++NumVisibleDeclContextsRead;
 
-  SetExternalVisibleDecls(DC, Decls);
+  SetExternalVisibleDeclsForName(DC, Name, Decls);
   return const_cast<DeclContext*>(DC)->lookup(Name);
 }
 
diff --git a/lib/Serialization/ASTReaderDecl.cpp b/lib/Serialization/ASTReaderDecl.cpp
index 9094281cd4..bc68e91e3e 100644
--- a/lib/Serialization/ASTReaderDecl.cpp
+++ b/lib/Serialization/ASTReaderDecl.cpp
@@ -1413,35 +1413,3 @@ Decl *ASTReader::ReadDeclRecord(unsigned Index, DeclID ID) {
 
   return D;
 }
-
-bool ASTReader::ReadDeclContextStorage(llvm::BitstreamCursor &Cursor,
-                                   const std::pair<uint64_t, uint64_t> &Offsets,
-                                       DeclContextInfo &Info) {
-  SavedStreamPosition SavedPosition(Cursor);
-  // First the lexical decls.
-  if (Offsets.first != 0) {
-    Cursor.JumpToBit(Offsets.first);
-
-    RecordData Record;
-    const char *Blob;
-    unsigned BlobLen;
-    unsigned Code = Cursor.ReadCode();
-    unsigned RecCode = Cursor.ReadRecord(Code, Record, &Blob, &BlobLen);
-    if (RecCode != DECL_CONTEXT_LEXICAL) {
-      Error("Expected lexical block");
-      return true;
-    }
-
-    Info.LexicalDecls = reinterpret_cast<const DeclID*>(Blob);
-    Info.NumLexicalDecls = BlobLen / sizeof(DeclID);
-  } else {
-    Info.LexicalDecls = 0;
-    Info.NumLexicalDecls = 0;
-  }
-
-  // Now the visible decls.
-  Info.Stream = &Cursor;
-  Info.OffsetToVisibleDecls = Offsets.second;
-
-  return false;
-}
diff --git a/lib/Serialization/ASTWriter.cpp b/lib/Serialization/ASTWriter.cpp
index 94be24ad2c..5deaf3d475 100644
--- a/lib/Serialization/ASTWriter.cpp
+++ b/lib/Serialization/ASTWriter.cpp
@@ -1466,59 +1466,6 @@ uint64_t ASTWriter::WriteDeclContextLexicalBlock(ASTContext &Context,
   return Offset;
 }
 
-/// \brief Write the block containing all of the declaration IDs
-/// visible from the given DeclContext.
-///
-/// \returns the offset of the DECL_CONTEXT_VISIBLE block within the
-/// bistream, or 0 if no block was written.
-uint64_t ASTWriter::WriteDeclContextVisibleBlock(ASTContext &Context,
-                                                 DeclContext *DC) {
-  if (DC->getPrimaryContext() != DC)
-    return 0;
-
-  // Since there is no name lookup into functions or methods, don't bother to
-  // build a visible-declarations table for these entities.
-  if (DC->isFunctionOrMethod())
-    return 0;
-
-  // If not in C++, we perform name lookup for the translation unit via the
-  // IdentifierInfo chains, don't bother to build a visible-declarations table.
-  // FIXME: In C++ we need the visible declarations in order to "see" the
-  // friend declarations, is there a way to do this without writing the table ?
-  if (DC->isTranslationUnit() && !Context.getLangOptions().CPlusPlus)
-    return 0;
-
-  // Force the DeclContext to build a its name-lookup table.
-  DC->lookup(DeclarationName());
-
-  // Serialize the contents of the mapping used for lookup. Note that,
-  // although we have two very different code paths, the serialized
-  // representation is the same for both cases: a declaration name,
-  // followed by a size, followed by references to the visible
-  // declarations that have that name.
-  uint64_t Offset = Stream.GetCurrentBitNo();
-  RecordData Record;
-  StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(DC->getLookupPtr());
-  if (!Map)
-    return 0;
-
-  for (StoredDeclsMap::iterator D = Map->begin(), DEnd = Map->end();
-       D != DEnd; ++D) {
-    AddDeclarationName(D->first, Record);
-    DeclContext::lookup_result Result = D->second.getLookupResult(Context);
-    Record.push_back(Result.second - Result.first);
-    for (; Result.first != Result.second; ++Result.first)
-      AddDeclRef(*Result.first, Record);
-  }
-
-  if (Record.size() == 0)
-    return 0;
-
-  Stream.EmitRecord(DECL_CONTEXT_VISIBLE, Record);
-  ++NumVisibleDeclContexts;
-  return Offset;
-}
-
 void ASTWriter::WriteTypeDeclOffsets() {
   using namespace llvm;
   RecordData Record;
@@ -2062,6 +2009,74 @@ public:
 };
 } // end anonymous namespace
 
+/// \brief Write the block containing all of the declaration IDs
+/// visible from the given DeclContext.
+///
+/// \returns the offset of the DECL_CONTEXT_VISIBLE block within the
+/// bistream, or 0 if no block was written.
+uint64_t ASTWriter::WriteDeclContextVisibleBlock(ASTContext &Context,
+                                                 DeclContext *DC) {
+  if (DC->getPrimaryContext() != DC)
+    return 0;
+
+  // Since there is no name lookup into functions or methods, don't bother to
+  // build a visible-declarations table for these entities.
+  if (DC->isFunctionOrMethod())
+    return 0;
+
+  // If not in C++, we perform name lookup for the translation unit via the
+  // IdentifierInfo chains, don't bother to build a visible-declarations table.
+  // FIXME: In C++ we need the visible declarations in order to "see" the
+  // friend declarations, is there a way to do this without writing the table ?
+  if (DC->isTranslationUnit() && !Context.getLangOptions().CPlusPlus)
+    return 0;
+
+  // Force the DeclContext to build a its name-lookup table.
+  DC->lookup(DeclarationName());
+
+  // Serialize the contents of the mapping used for lookup. Note that,
+  // although we have two very different code paths, the serialized
+  // representation is the same for both cases: a declaration name,
+  // followed by a size, followed by references to the visible
+  // declarations that have that name.
+  uint64_t Offset = Stream.GetCurrentBitNo();
+  StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(DC->getLookupPtr());
+  if (!Map || Map->empty())
+    return 0;
+
+  OnDiskChainedHashTableGenerator<ASTDeclContextNameLookupTrait> Generator;
+  ASTDeclContextNameLookupTrait Trait(*this);
+
+  // Create the on-disk hash table representation.
+  for (StoredDeclsMap::iterator D = Map->begin(), DEnd = Map->end();
+       D != DEnd; ++D) {
+    DeclarationName Name = D->first;
+    DeclContext::lookup_result Result = D->second.getLookupResult();
+    Generator.insert(Name, Result, Trait);
+  }
+
+  // Create the on-disk hash table in a buffer.
+  llvm::SmallString<4096> LookupTable;
+  uint32_t BucketOffset;
+  {
+    llvm::raw_svector_ostream Out(LookupTable);
+    // Make sure that no bucket is at offset 0
+    clang::io::Emit32(Out, 0);
+    BucketOffset = Generator.Emit(Out, Trait);
+  }
+
+  // Write the lookup table
+  RecordData Record;
+  Record.push_back(DECL_CONTEXT_VISIBLE);
+  Record.push_back(BucketOffset);
+  Stream.EmitRecordWithBlob(DeclContextVisibleLookupAbbrev, Record,
+                            LookupTable.str());
+
+  Stream.EmitRecord(DECL_CONTEXT_VISIBLE, Record);
+  ++NumVisibleDeclContexts;
+  return Offset;
+}
+
 //===----------------------------------------------------------------------===//
 // General Serialization Routines
 //===----------------------------------------------------------------------===//
diff --git a/lib/Serialization/ASTWriterDecl.cpp b/lib/Serialization/ASTWriterDecl.cpp
index 016f4d3c73..a5d2ce21c2 100644
--- a/lib/Serialization/ASTWriterDecl.cpp
+++ b/lib/Serialization/ASTWriterDecl.cpp
@@ -1086,6 +1086,12 @@ void ASTWriter::WriteDeclsBlockAbbrevs() {
   Abv->Add(BitCodeAbbrevOp(serialization::DECL_CONTEXT_LEXICAL));
   Abv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
   DeclContextLexicalAbbrev = Stream.EmitAbbrev(Abv);
+
+  Abv = new BitCodeAbbrev();
+  Abv->Add(BitCodeAbbrevOp(serialization::DECL_CONTEXT_VISIBLE));
+  Abv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
+  Abv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
+  DeclContextVisibleLookupAbbrev = Stream.EmitAbbrev(Abv);
 }
 
 /// isRequiredDecl - Check if this is a "required" Decl, which must be seen by