Add better ODR checking for modules.

Recommit r293585 that was reverted in r293611 with new fixes.  The previous
issue was determined to be an overly aggressive AST visitor from forward
declared objects.  The visitor will now only deeply visit certain Decl's and
only do a shallow information extraction from all other Decl's.

When objects are imported for modules, there is a chance that a name collision
will cause an ODR violation.  Previously, only a small number of such
violations were detected.  This patch provides a stronger check based on
AST nodes.

The information needed to uniquely identify an object is taken from the AST and
put into a one-dimensional byte stream.  This stream is then hashed to give
a value to represent the object, which is stored with the other object data
in the module.

When modules are loaded, and Decl's are merged, the hash values of the two
Decl's are compared.  Only Decl's with matched hash values will be merged.
Mismatch hashes will generate a module error, and if possible, point to the
first difference between the two objects.

The transform from AST to byte stream is a modified depth first algorithm.
Due to references between some AST nodes, a pure depth first algorithm could
generate loops.  For Stmt nodes, a straight depth first processing occurs.
For Type and Decl nodes, they are replaced with an index number and only on
first visit will these nodes be processed.  As an optimization, boolean
values are saved and stored together in reverse order at the end of the
byte stream to lower the ammount of data that needs to be hashed.

Compile time impact was measured at 1.5-2.0% during module building, and
negligible during builds without module building.

Differential Revision: https://reviews.llvm.org/D21675

llvm-svn: 295284

1 files changed, 145 insertions, 84 deletions

diff --git a/clang/lib/AST/StmtProfile.cpp b/clang/lib/AST/StmtProfile.cpp
index 49e43de638a0..1ac2a5bf5e1d 100644
--- a/clang/lib/AST/StmtProfile.cpp
+++ b/clang/lib/AST/StmtProfile.cpp
@@ -19,20 +19,22 @@
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/ExprObjC.h"
 #include "clang/AST/ExprOpenMP.h"
+#include "clang/AST/ODRHash.h"
 #include "clang/AST/StmtVisitor.h"
 #include "llvm/ADT/FoldingSet.h"
 using namespace clang;
 
 namespace {
   class StmtProfiler : public ConstStmtVisitor<StmtProfiler> {
+  protected:
     llvm::FoldingSetNodeID &ID;
-    const ASTContext &Context;
     bool Canonical;
 
   public:
-    StmtProfiler(llvm::FoldingSetNodeID &ID, const ASTContext &Context,
-                 bool Canonical)
-      : ID(ID), Context(Context), Canonical(Canonical) { }
+    StmtProfiler(llvm::FoldingSetNodeID &ID, bool Canonical)
+        : ID(ID), Canonical(Canonical) {}
+
+    virtual ~StmtProfiler() {}
 
     void VisitStmt(const Stmt *S);
 
@@ -41,22 +43,25 @@ namespace {
 
     /// \brief Visit a declaration that is referenced within an expression
     /// or statement.
-    void VisitDecl(const Decl *D);
+    virtual void VisitDecl(const Decl *D) = 0;
 
     /// \brief Visit a type that is referenced within an expression or
     /// statement.
-    void VisitType(QualType T);
+    virtual void VisitType(QualType T) = 0;
 
     /// \brief Visit a name that occurs within an expression or statement.
-    void VisitName(DeclarationName Name);
+    virtual void VisitName(DeclarationName Name) = 0;
+
+    /// \brief Visit identifiers that are not in Decl's or Type's.
+    virtual void VisitIdentifierInfo(IdentifierInfo *II) = 0;
 
     /// \brief Visit a nested-name-specifier that occurs within an expression
     /// or statement.
-    void VisitNestedNameSpecifier(NestedNameSpecifier *NNS);
+    virtual void VisitNestedNameSpecifier(NestedNameSpecifier *NNS) = 0;
 
     /// \brief Visit a template name that occurs within an expression or
     /// statement.
-    void VisitTemplateName(TemplateName Name);
+    virtual void VisitTemplateName(TemplateName Name) = 0;
 
     /// \brief Visit template arguments that occur within an expression or
     /// statement.
@@ -66,6 +71,127 @@ namespace {
     /// \brief Visit a single template argument.
     void VisitTemplateArgument(const TemplateArgument &Arg);
   };
+
+  class StmtProfilerWithPointers : public StmtProfiler {
+    const ASTContext &Context;
+
+  public:
+    StmtProfilerWithPointers(llvm::FoldingSetNodeID &ID,
+                             const ASTContext &Context, bool Canonical)
+        : StmtProfiler(ID, Canonical), Context(Context) {}
+  private:
+    void VisitDecl(const Decl *D) override {
+      ID.AddInteger(D ? D->getKind() : 0);
+
+      if (Canonical && D) {
+        if (const NonTypeTemplateParmDecl *NTTP =
+                dyn_cast<NonTypeTemplateParmDecl>(D)) {
+          ID.AddInteger(NTTP->getDepth());
+          ID.AddInteger(NTTP->getIndex());
+          ID.AddBoolean(NTTP->isParameterPack());
+          VisitType(NTTP->getType());
+          return;
+        }
+
+        if (const ParmVarDecl *Parm = dyn_cast<ParmVarDecl>(D)) {
+          // The Itanium C++ ABI uses the type, scope depth, and scope
+          // index of a parameter when mangling expressions that involve
+          // function parameters, so we will use the parameter's type for
+          // establishing function parameter identity. That way, our
+          // definition of "equivalent" (per C++ [temp.over.link]) is at
+          // least as strong as the definition of "equivalent" used for
+          // name mangling.
+          VisitType(Parm->getType());
+          ID.AddInteger(Parm->getFunctionScopeDepth());
+          ID.AddInteger(Parm->getFunctionScopeIndex());
+          return;
+        }
+
+        if (const TemplateTypeParmDecl *TTP =
+                dyn_cast<TemplateTypeParmDecl>(D)) {
+          ID.AddInteger(TTP->getDepth());
+          ID.AddInteger(TTP->getIndex());
+          ID.AddBoolean(TTP->isParameterPack());
+          return;
+        }
+
+        if (const TemplateTemplateParmDecl *TTP =
+                dyn_cast<TemplateTemplateParmDecl>(D)) {
+          ID.AddInteger(TTP->getDepth());
+          ID.AddInteger(TTP->getIndex());
+          ID.AddBoolean(TTP->isParameterPack());
+          return;
+        }
+      }
+
+      ID.AddPointer(D ? D->getCanonicalDecl() : nullptr);
+    }
+
+    void VisitType(QualType T) override {
+      if (Canonical)
+        T = Context.getCanonicalType(T);
+
+      ID.AddPointer(T.getAsOpaquePtr());
+    }
+
+    void VisitName(DeclarationName Name) override {
+      ID.AddPointer(Name.getAsOpaquePtr());
+    }
+
+    void VisitIdentifierInfo(IdentifierInfo *II) override {
+      ID.AddPointer(II);
+    }
+
+    void VisitNestedNameSpecifier(NestedNameSpecifier *NNS) override {
+      if (Canonical)
+        NNS = Context.getCanonicalNestedNameSpecifier(NNS);
+      ID.AddPointer(NNS);
+    }
+
+    void VisitTemplateName(TemplateName Name) override {
+      if (Canonical)
+        Name = Context.getCanonicalTemplateName(Name);
+
+      Name.Profile(ID);
+    }
+  };
+
+  class StmtProfilerWithoutPointers : public StmtProfiler {
+    ODRHash &Hash;
+  public:
+    StmtProfilerWithoutPointers(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
+        : StmtProfiler(ID, false), Hash(Hash) {}
+
+  private:
+    void VisitType(QualType T) override {
+      Hash.AddQualType(T);
+    }
+
+    void VisitName(DeclarationName Name) override {
+      Hash.AddDeclarationName(Name);
+    }
+    void VisitIdentifierInfo(IdentifierInfo *II) override {
+      ID.AddBoolean(II);
+      if (II) {
+        Hash.AddIdentifierInfo(II);
+      }
+    }
+    void VisitDecl(const Decl *D) override {
+      ID.AddBoolean(D);
+      if (D) {
+        Hash.AddDecl(D);
+      }
+    }
+    void VisitTemplateName(TemplateName Name) override {
+      Hash.AddTemplateName(Name);
+    }
+    void VisitNestedNameSpecifier(NestedNameSpecifier *NNS) override {
+      ID.AddBoolean(NNS);
+      if (NNS) {
+        Hash.AddNestedNameSpecifier(NNS);
+      }
+    }
+  };
 }
 
 void StmtProfiler::VisitStmt(const Stmt *S) {
@@ -853,7 +979,7 @@ void StmtProfiler::VisitOffsetOfExpr(const OffsetOfExpr *S) {
       break;
 
     case OffsetOfNode::Identifier:
-      ID.AddPointer(ON.getFieldName());
+      VisitIdentifierInfo(ON.getFieldName());
       break;
 
     case OffsetOfNode::Base:
@@ -861,7 +987,7 @@ void StmtProfiler::VisitOffsetOfExpr(const OffsetOfExpr *S) {
       break;
     }
   }
-  
+
   VisitExpr(S);
 }
 
@@ -1451,7 +1577,7 @@ StmtProfiler::VisitCXXPseudoDestructorExpr(const CXXPseudoDestructorExpr *S) {
   if (S->getDestroyedTypeInfo())
     VisitType(S->getDestroyedType());
   else
-    ID.AddPointer(S->getDestroyedTypeIdentifier());
+    VisitIdentifierInfo(S->getDestroyedTypeIdentifier());
 }
 
 void StmtProfiler::VisitOverloadExpr(const OverloadExpr *S) {
@@ -1701,77 +1827,6 @@ void StmtProfiler::VisitObjCAvailabilityCheckExpr(
   VisitExpr(S);
 }
 
-void StmtProfiler::VisitDecl(const Decl *D) {
-  ID.AddInteger(D? D->getKind() : 0);
-
-  if (Canonical && D) {
-    if (const NonTypeTemplateParmDecl *NTTP =
-          dyn_cast<NonTypeTemplateParmDecl>(D)) {
-      ID.AddInteger(NTTP->getDepth());
-      ID.AddInteger(NTTP->getIndex());
-      ID.AddBoolean(NTTP->isParameterPack());
-      VisitType(NTTP->getType());
-      return;
-    }
-
-    if (const ParmVarDecl *Parm = dyn_cast<ParmVarDecl>(D)) {
-      // The Itanium C++ ABI uses the type, scope depth, and scope
-      // index of a parameter when mangling expressions that involve
-      // function parameters, so we will use the parameter's type for
-      // establishing function parameter identity. That way, our
-      // definition of "equivalent" (per C++ [temp.over.link]) is at
-      // least as strong as the definition of "equivalent" used for
-      // name mangling.
-      VisitType(Parm->getType());
-      ID.AddInteger(Parm->getFunctionScopeDepth());
-      ID.AddInteger(Parm->getFunctionScopeIndex());
-      return;
-    }
-
-    if (const TemplateTypeParmDecl *TTP =
-          dyn_cast<TemplateTypeParmDecl>(D)) {
-      ID.AddInteger(TTP->getDepth());
-      ID.AddInteger(TTP->getIndex());
-      ID.AddBoolean(TTP->isParameterPack());
-      return;
-    }
-
-    if (const TemplateTemplateParmDecl *TTP =
-          dyn_cast<TemplateTemplateParmDecl>(D)) {
-      ID.AddInteger(TTP->getDepth());
-      ID.AddInteger(TTP->getIndex());
-      ID.AddBoolean(TTP->isParameterPack());
-      return;
-    }
-  }
-
-  ID.AddPointer(D? D->getCanonicalDecl() : nullptr);
-}
-
-void StmtProfiler::VisitType(QualType T) {
-  if (Canonical)
-    T = Context.getCanonicalType(T);
-
-  ID.AddPointer(T.getAsOpaquePtr());
-}
-
-void StmtProfiler::VisitName(DeclarationName Name) {
-  ID.AddPointer(Name.getAsOpaquePtr());
-}
-
-void StmtProfiler::VisitNestedNameSpecifier(NestedNameSpecifier *NNS) {
-  if (Canonical)
-    NNS = Context.getCanonicalNestedNameSpecifier(NNS);
-  ID.AddPointer(NNS);
-}
-
-void StmtProfiler::VisitTemplateName(TemplateName Name) {
-  if (Canonical)
-    Name = Context.getCanonicalTemplateName(Name);
-
-  Name.Profile(ID);
-}
-
 void StmtProfiler::VisitTemplateArguments(const TemplateArgumentLoc *Args,
                                           unsigned NumArgs) {
   ID.AddInteger(NumArgs);
@@ -1821,6 +1876,12 @@ void StmtProfiler::VisitTemplateArgument(const TemplateArgument &Arg) {
 
 void Stmt::Profile(llvm::FoldingSetNodeID &ID, const ASTContext &Context,
                    bool Canonical) const {
-  StmtProfiler Profiler(ID, Context, Canonical);
+  StmtProfilerWithPointers Profiler(ID, Context, Canonical);
+  Profiler.Visit(this);
+}
+
+void Stmt::ProcessODRHash(llvm::FoldingSetNodeID &ID,
+                          class ODRHash &Hash) const {
+  StmtProfilerWithoutPointers Profiler(ID, Hash);
   Profiler.Visit(this);
 }