Shrink DynTypedNode by one pointer from 40 to 32 bytes (on x86_64).

[bkramer]

Summary

The MemoizationData cache was introduced to avoid a series of enum
compares at the cost of making DynTypedNode bigger. This change reverts
to using an enum compare but instead of building a chain of comparison
the enum values are reordered so the check can be performed with a
simple greater than. The alternative would be to steal a bit from the
enum but I think that's a more complex solution and not really needed
here.

I tried this on several large .cpp files with clang-tidy and didn't
notice any performance difference. The test change is due to matchers
being sorted by their node kind.

[sbenza]

include/clang/AST/ASTTypeTraits.h

250

I'm not sure about this reinterpret_cast.
We are not storing void*. We are storing 'const Node*'.
I think this way is UB.

Maybe we should modify the union and the create/getUnchecked methods to use 'const void*' as storage instead.
Instead of:

new (Result.Storage.buffer) const BaseT * (&Node);
...
return *cast<T>(*reinterpret_cast<BaseT *const *>(Storage));

we should do

new (Result.Storage.buffer) const void * (static_cast<const BaseT*>(&Node));
...
return *cast<T>(static_cast<const BaseT*>(*reinterpret_cast<const void *const *>(Storage)));

[bkramer]

Update casts to avoid potential undefined behavior. Now every pointer goes through const void*.

[sbenza]

include/clang/AST/ASTTypeTraits.h

300

maybe call getUnchecked() to avoid duplication?
Now it is getting complicated.

include/clang/AST/ASTTypeTraits.h

static inline ASTNodeKind getTombstoneKey() {
       return ASTNodeKind(NKI_NumberOfKinds);
     }
     static unsigned getHashValue(const ASTNodeKind &Val) { return Val.KindId; }
     static bool isEqual(const ASTNodeKind &LHS, const ASTNodeKind &RHS) {
       return LHS.KindId == RHS.KindId;
     }
   };
 
+  /// Check if the given ASTNodeKind identifies a type that offers pointer
+  /// identity. This is useful for the fast path in DynTypedNode.
+  bool hasPointerIdentity() const {
+    return KindId > NKI_LastKindWithoutPointerIdentity;
+  }
+
 private:
   /// \brief Kind ids.
   ///
   /// Includes all possible base and derived kinds.
   enum NodeKindId {
     NKI_None,
-    NKI_CXXCtorInitializer,
     NKI_TemplateArgument,
-    NKI_NestedNameSpecifier,
     NKI_NestedNameSpecifierLoc,
     NKI_QualType,
     NKI_TypeLoc,
+    NKI_LastKindWithoutPointerIdentity = NKI_TypeLoc,
+    NKI_CXXCtorInitializer,
+    NKI_NestedNameSpecifier,
     NKI_Decl,
 #define DECL(DERIVED, BASE) NKI_##DERIVED##Decl,
 #include "clang/AST/DeclNodes.inc"
     NKI_Stmt,
 #define STMT(DERIVED, BASE) NKI_##DERIVED,
 #include "clang/AST/StmtNodes.inc"
     NKI_Type,
 #define TYPE(DERIVED, BASE) NKI_##DERIVED##Type,
public:
 
   ASTNodeKind getNodeKind() const { return NodeKind; }
 
   /// \brief Returns a pointer that identifies the stored AST node.
   ///
   /// Note that this is not supported by all AST nodes. For AST nodes
   /// that don't have a pointer-defined identity inside the AST, this
   /// method returns NULL.
-  const void *getMemoizationData() const { return MemoizationData; }
+  const void *getMemoizationData() const {
+    return NodeKind.hasPointerIdentity()
+               ? *reinterpret_cast<void *const *>(Storage.buffer)
+               : nullptr;
+  }
 
   /// \brief Prints the node to the given output stream.
   void print(llvm::raw_ostream &OS, const PrintingPolicy &PP) const;
 
   /// \brief Dumps the node to the given output stream.
   void dump(llvm::raw_ostream &OS, SourceManager &SM) const;
 
   /// \brief For nodes which represent textual entities in the source code,

 private:
   /// \brief Takes care of converting from and to \c T.
   template <typename T, typename EnablerT = void> struct BaseConverter;
 
   /// \brief Converter that uses dyn_cast<T> from a stored BaseT*.
   template <typename T, typename BaseT> struct DynCastPtrConverter {
     static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
       if (ASTNodeKind::getFromNodeKind<T>().isBaseOf(NodeKind))
-        return cast<T>(*reinterpret_cast<BaseT *const *>(Storage));
+        return cast<T>(static_cast<const BaseT *>(
+            *reinterpret_cast<const void *const *>(Storage)));
       return nullptr;
     }
     static const T &getUnchecked(ASTNodeKind NodeKind, const char Storage[]) {
       assert(ASTNodeKind::getFromNodeKind<T>().isBaseOf(NodeKind));
-      return *cast<T>(*reinterpret_cast<BaseT *const *>(Storage));
+      return *cast<T>(static_cast<const BaseT *>(
+          *reinterpret_cast<const void *const *>(Storage)));
     }
     static DynTypedNode create(const BaseT &Node) {
       DynTypedNode Result;
       Result.NodeKind = ASTNodeKind::getFromNode(Node);
-      Result.MemoizationData = &Node;
-      new (Result.Storage.buffer) const BaseT * (&Node);
+      new (Result.Storage.buffer) const void *(&Node);
       return Result;
     }
   };
 
   /// \brief Converter that stores T* (by pointer).
   template <typename T> struct PtrConverter {
     static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
       if (ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind))
         return *reinterpret_cast<T *const *>(Storage);
       return nullptr;
     }
     static const T &getUnchecked(ASTNodeKind NodeKind, const char Storage[]) {
       assert(ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind));
-      return **reinterpret_cast<T *const *>(Storage);
+      return *static_cast<const T *>(
+          *reinterpret_cast<const void *const *>(Storage));
     }
     static DynTypedNode create(const T &Node) {
       DynTypedNode Result;
       Result.NodeKind = ASTNodeKind::getFromNodeKind<T>();
-      Result.MemoizationData = &Node;
-      new (Result.Storage.buffer) const T * (&Node);
+      new (Result.Storage.buffer) const void *(&Node);
       return Result;
     }
   };
 
   /// \brief Converter that stores T (by value).
   template <typename T> struct ValueConverter {
     static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
       if (ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind))
         return reinterpret_cast<const T *>(Storage);
       return nullptr;
     }
     static const T &getUnchecked(ASTNodeKind NodeKind, const char Storage[]) {
       assert(ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind));
       return *reinterpret_cast<const T *>(Storage);
     }
     static DynTypedNode create(const T &Node) {
       DynTypedNode Result;
       Result.NodeKind = ASTNodeKind::getFromNodeKind<T>();
-      Result.MemoizationData = nullptr;
       new (Result.Storage.buffer) T(Node);
       return Result;
     }
   };
 
   ASTNodeKind NodeKind;
-  const void *MemoizationData;
 
   /// \brief Stores the data of the node.
   ///
   /// Note that we can store \c Decls, \c Stmts, \c Types,
   /// \c NestedNameSpecifiers and \c CXXCtorInitializer by pointer as they are
   /// guaranteed to be unique pointers pointing to dedicated storage in the AST.
   /// \c QualTypes, \c NestedNameSpecifierLocs, \c TypeLocs and
   /// \c TemplateArguments on the other hand do not have storage or unique
   /// pointers and thus need to be stored by value.
-  typedef llvm::AlignedCharArrayUnion<
-      Decl *, Stmt *, Type *, NestedNameSpecifier *, CXXCtorInitializer *>
-      KindsByPointer;
-  llvm::AlignedCharArrayUnion<KindsByPointer, TemplateArgument,
-                              NestedNameSpecifierLoc, QualType, TypeLoc>
-      Storage;
+  llvm::AlignedCharArrayUnion<const void *, TemplateArgument,
+                              NestedNameSpecifierLoc, QualType,
+                              TypeLoc> Storage;
 };
 
 template <typename T>
 struct DynTypedNode::BaseConverter<
     T, typename std::enable_if<std::is_base_of<Decl, T>::value>::type>
     : public DynCastPtrConverter<T, Decl> {};
 
 template <typename T>

unittests/ASTMatchers/Dynamic/RegistryTest.cpp

TEST_F(RegistryTest, Completion) {
   EXPECT_TRUE(hasCompletion(
       Comps, "hasParent(", "Matcher<Decl|Stmt> hasParent(Matcher<Decl|Stmt>)"));
   // Variadic.
   EXPECT_TRUE(hasCompletion(Comps, "whileStmt(",
                             "Matcher<Stmt> whileStmt(Matcher<WhileStmt>...)"));
   // Polymorphic.
   EXPECT_TRUE(hasCompletion(
       Comps, "hasDescendant(",
-      "Matcher<NestedNameSpecifier|NestedNameSpecifierLoc|QualType|...> "
-      "hasDescendant(Matcher<CXXCtorInitializer|NestedNameSpecifier|"
+      "Matcher<TemplateArgument|NestedNameSpecifier|NestedNameSpecifierLoc|...>"
+      " hasDescendant(Matcher<TemplateArgument|NestedNameSpecifier|"
       "NestedNameSpecifierLoc|...>)"));
 
   CompVector WhileComps = getCompletions("whileStmt", 0);
 
   EXPECT_TRUE(hasCompletion(WhileComps, "hasBody(",
                             "Matcher<WhileStmt> hasBody(Matcher<Stmt>)"));
   EXPECT_TRUE(hasCompletion(WhileComps, "hasParent(",
                             "Matcher<Stmt> hasParent(Matcher<Decl|Stmt>)"));