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


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

3 files changed, 91 insertions, 0 deletions

diff --git a/include/clang/AST/DeclCXX.h b/include/clang/AST/DeclCXX.h
index 020ebfb4af..c8db319f9d 100644
--- a/include/clang/AST/DeclCXX.h
+++ b/include/clang/AST/DeclCXX.h
@@ -458,6 +458,9 @@ class CXXRecordDecl : public RecordDecl {
     /// \brief Whether we are currently parsing base specifiers.
     unsigned IsParsingBaseSpecifiers : 1;
 
+    /// \brief A hash of parts of the class to help in ODR checking.
+    unsigned ODRHash;
+
     /// \brief The number of base class specifiers in Bases.
     unsigned NumBases;
 
@@ -703,6 +706,9 @@ public:
     return data().IsParsingBaseSpecifiers;
   }
 
+  void computeODRHash();
+  unsigned getODRHash() const { return data().ODRHash; }
+
   /// \brief Sets the base classes of this struct or class.
   void setBases(CXXBaseSpecifier const * const *Bases, unsigned NumBases);
 
diff --git a/include/clang/AST/ODRHash.h b/include/clang/AST/ODRHash.h
new file mode 100644
index 0000000000..f600a17865
--- /dev/null
+++ b/include/clang/AST/ODRHash.h
@@ -0,0 +1,82 @@
+//===-- ODRHash.h - Hashing to diagnose ODR failures ------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This file contains the declaration of the ODRHash class, which calculates
+/// a hash based on AST nodes, which is stable across different runs.
+///
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/DeclarationName.h"
+#include "clang/AST/Type.h"
+#include "clang/AST/TemplateBase.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/PointerUnion.h"
+#include "llvm/ADT/SmallVector.h"
+
+namespace clang {
+
+class Decl;
+class IdentifierInfo;
+class NestedNameSpecifer;
+class Stmt;
+class TemplateParameterList;
+
+// ODRHash is used to calculate a hash based on AST node contents that
+// does not rely on pointer addresses.  This allows the hash to not vary
+// between runs and is usable to detect ODR problems in modules.  To use,
+// construct an ODRHash object, then call Add* methods over the nodes that
+// need to be hashed.  Then call CalculateHash to get the hash value.
+// Typically, only one Add* call is needed.  clear can be called to reuse the
+// object.
+class ODRHash {
+  // Use DenseMaps to convert between Decl and Type pointers and an index value.
+  llvm::DenseMap<const Decl*, unsigned> DeclMap;
+  llvm::DenseMap<const Type*, unsigned> TypeMap;
+
+  // Save space by processing bools at the end.
+  llvm::SmallVector<bool, 128> Bools;
+
+  llvm::FoldingSetNodeID ID;
+
+public:
+  ODRHash() {}
+
+  // Use this for ODR checking classes between modules.  This method compares
+  // more information than the AddDecl class.
+  void AddCXXRecordDecl(const CXXRecordDecl *Record);
+
+  // Process SubDecls of the main Decl.  This method calls the DeclVisitor
+  // while AddDecl does not.
+  void AddSubDecl(const Decl *D);
+
+  // Reset the object for reuse.
+  void clear();
+
+  // Add booleans to ID and uses it to calculate the hash.
+  unsigned CalculateHash();
+
+  // Add AST nodes that need to be processed.
+  void AddDecl(const Decl *D);
+  void AddType(const Type *T);
+  void AddQualType(QualType T);
+  void AddStmt(const Stmt *S);
+  void AddIdentifierInfo(const IdentifierInfo *II);
+  void AddNestedNameSpecifier(const NestedNameSpecifier *NNS);
+  void AddTemplateName(TemplateName Name);
+  void AddDeclarationName(DeclarationName Name);
+  void AddTemplateArgument(TemplateArgument TA);
+  void AddTemplateParameterList(const TemplateParameterList *TPL);
+
+  // Save booleans until the end to lower the size of data to process.
+  void AddBoolean(bool value);
+};
+
+}  // end namespace clang
diff --git a/include/clang/AST/Stmt.h b/include/clang/AST/Stmt.h
index e28675d6a8..defe6c2ac2 100644
--- a/include/clang/AST/Stmt.h
+++ b/include/clang/AST/Stmt.h
@@ -39,6 +39,7 @@ namespace clang {
   class Expr;
   class IdentifierInfo;
   class LabelDecl;
+  class ODRHash;
   class ParmVarDecl;
   class PrinterHelper;
   struct PrintingPolicy;
@@ -436,6 +437,8 @@ public:
   /// written in the source.
   void Profile(llvm::FoldingSetNodeID &ID, const ASTContext &Context,
                bool Canonical) const;
+
+  void ProcessODRHash(llvm::FoldingSetNodeID &ID, ODRHash& Hash) const;
 };
 
 /// DeclStmt - Adaptor class for mixing declarations with statements and