[AST] Store Decl* and Stmt* directly into the ParentMap.

[bkramer]

Summary

These are by far the most common types to be parents in the AST so it makes
sense to optimize for them. Put them directly into the value of the map.
This currently saves 32 bytes per parent in the map and a pointer
indirection at the cost of some additional complexity in the code.

Sadly this means we cannot return an ArrayRef from getParents anymore, add
a proxy class that can own a single DynTypedNode and otherwise behaves
exactly the same as ArrayRef.

For example on a random large file (X86ISelLowering.cpp) this reduces the size
of the parent map by 24 MB.

[klimek]

lg

include/clang/AST/ASTContext.h

463

I think "using" is clearer.

464

Show me what ArrayRef<DynTypedNode> looks like written out below :)

include/clang/AST/ASTContext.h

public:
   IntrusiveRefCntPtr<ExternalASTSource> ExternalSource;
   ASTMutationListener *Listener;
 
   /// \brief Contains parents of a node.
   typedef llvm::SmallVector<ast_type_traits::DynTypedNode, 2> ParentVector;
 
   /// \brief Maps from a node to its parents.
   typedef llvm::DenseMap<const void *,
-                         llvm::PointerUnion<ast_type_traits::DynTypedNode *,
+                         llvm::PointerUnion4<const Decl *, const Stmt *,
+                                             ast_type_traits::DynTypedNode *,
                                              ParentVector *>> ParentMap;
 
+  /// Container for either a single DynTypedNode or for an ArrayRef to
+  /// DynTypedNode. For use with ParentMap.
+  class DynTypedNodeList {
+    typedef ast_type_traits::DynTypedNode DynTypedNode;
+    typedef ArrayRef<DynTypedNode> ARef;
+    llvm::AlignedCharArrayUnion<ast_type_traits::DynTypedNode, ARef> Storage;
+    bool IsSingleNode;
+
+  public:
+    DynTypedNodeList(const DynTypedNode &N) : IsSingleNode(true) {
+      new (Storage.buffer) DynTypedNode(N);
+    }
+    DynTypedNodeList(ARef A) : IsSingleNode(false) {
+      new (Storage.buffer) ARef(A);
+    }
+
+    const ast_type_traits::DynTypedNode *begin() const {
+      if (!IsSingleNode)
+        return reinterpret_cast<const ARef *>(Storage.buffer)->begin();
+      return reinterpret_cast<const DynTypedNode *>(Storage.buffer);
+    }
+
+    const ast_type_traits::DynTypedNode *end() const {
+      if (!IsSingleNode)
+        return reinterpret_cast<const ARef *>(Storage.buffer)->end();
+      return reinterpret_cast<const DynTypedNode *>(Storage.buffer) + 1;
+    }
+
+    size_t size() const { return end() - begin(); }
+    bool empty() const { return begin() == end(); }
+    const ast_type_traits::DynTypedNode &operator[](size_t N) const {
+      assert(N < size() && "Out of bounds!");
+      return *(begin() + N);
+    }
+  };
+
   /// \brief Returns the parents of the given node.
   ///
   /// Note that this will lazily compute the parents of all nodes
   /// and store them for later retrieval. Thus, the first call is O(n)
   /// in the number of AST nodes.
   ///
   /// Caveats and FIXMEs:
   /// Calculating the parent map over all AST nodes will need to load the
   /// full AST. This can be undesirable in the case where the full AST is
   /// expensive to create (for example, when using precompiled header
   /// preambles). Thus, there are good opportunities for optimization here.
   /// One idea is to walk the given node downwards, looking for references
   /// to declaration contexts - once a declaration context is found, compute
   /// the parent map for the declaration context; if that can satisfy the
   /// request, loading the whole AST can be avoided. Note that this is made
   /// more complex by statements in templates having multiple parents - those
   /// problems can be solved by building closure over the templated parts of
   /// the AST, which also avoids touching large parts of the AST.
   /// Additionally, we will want to add an interface to already give a hint
   /// where to search for the parents, for example when looking at a statement
   /// inside a certain function.
   ///
   /// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc,
   /// NestedNameSpecifier or NestedNameSpecifierLoc.
-  template <typename NodeT>
-  ArrayRef<ast_type_traits::DynTypedNode> getParents(const NodeT &Node) {
+  template <typename NodeT> DynTypedNodeList getParents(const NodeT &Node) {
     return getParents(ast_type_traits::DynTypedNode::create(Node));
   }
 
-  ArrayRef<ast_type_traits::DynTypedNode>
-  getParents(const ast_type_traits::DynTypedNode &Node);
+  DynTypedNodeList getParents(const ast_type_traits::DynTypedNode &Node);
 
   const clang::PrintingPolicy &getPrintingPolicy() const {
     return PrintingPolicy;
   }
 
   void setPrintingPolicy(const clang::PrintingPolicy &Policy) {
     PrintingPolicy = Policy;
   }

lib/AST/ASTContext.cpp

ASTContext::~ASTContext() {
   llvm::DeleteContainerSeconds(MangleNumberingContexts);
 }
 
 void ASTContext::ReleaseParentMapEntries() {
   if (!AllParents) return;
   for (const auto &Entry : *AllParents) {
     if (Entry.second.is<ast_type_traits::DynTypedNode *>()) {
       delete Entry.second.get<ast_type_traits::DynTypedNode *>();
-    } else {
-      assert(Entry.second.is<ParentVector *>());
+    } else if (Entry.second.is<ParentVector *>()) {
       delete Entry.second.get<ParentVector *>();
     }
   }
 }
 
 void ASTContext::AddDeallocation(void (*Callback)(void*), void *Data) {
   Deallocations[Callback].push_back(Data);
 }
bool ASTContext::AtomicUsesUnsupportedLibcall(const AtomicExpr *E) const {
   CharUnits alignChars = getTypeAlignInChars(AtomicTy);
   unsigned Align = alignChars.getQuantity();
   unsigned MaxInlineWidthInBits = getTargetInfo().getMaxAtomicInlineWidth();
   return (Size != Align || toBits(sizeChars) > MaxInlineWidthInBits);
 }
 
 namespace {
 
+ast_type_traits::DynTypedNode
+getSingleDynTypedNodeFromParentMap(ASTContext::ParentMap::mapped_type U) {
+  if (const auto *D = U.template dyn_cast<const Decl *>())
+    return ast_type_traits::DynTypedNode::create(*D);
+  if (const auto *S = U.template dyn_cast<const Stmt *>())
+    return ast_type_traits::DynTypedNode::create(*S);
+  return *U.template get<ast_type_traits::DynTypedNode *>();
+}
+
   /// \brief A \c RecursiveASTVisitor that builds a map from nodes to their
   /// parents as defined by the \c RecursiveASTVisitor.
   ///
   /// Note that the relationship described here is purely in terms of AST
   /// traversal - there are other relationships (for example declaration context)
   /// in the AST that are better modeled by special matchers.
   ///
   /// FIXME: Currently only builds up the map using \c Stmt and \c Decl nodes.
bool TraverseNode(T *Node, bool(VisitorBase:: *traverse) (T *)) {
         // visit those is with hasAncestor / hasParent, and those do not create
         // new matches.
         // The plan is to enable DynTypedNode to be storable in a map or hash
         // map. The main problem there is to implement hash functions /
         // comparison operators for all types that DynTypedNode supports that
         // do not have pointer identity.
         auto &NodeOrVector = (*Parents)[Node];
         if (NodeOrVector.isNull()) {
-          NodeOrVector = new ast_type_traits::DynTypedNode(ParentStack.back());
+          if (const auto *D = ParentStack.back().get<Decl>())
+            NodeOrVector = D;
+          else if (const auto *S = ParentStack.back().get<Stmt>())
+            NodeOrVector = S;
+          else
+            NodeOrVector =
+                new ast_type_traits::DynTypedNode(ParentStack.back());
         } else {
-          if (NodeOrVector.template is<ast_type_traits::DynTypedNode *>()) {
-            auto *Node =
-                NodeOrVector.template get<ast_type_traits::DynTypedNode *>();
-            auto *Vector = new ASTContext::ParentVector(1, *Node);
+          if (!NodeOrVector.template is<ASTContext::ParentVector *>()) {
+            auto *Vector = new ASTContext::ParentVector(
+                1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
             NodeOrVector = Vector;
+            if (auto *Node =
+                    NodeOrVector
+                        .template dyn_cast<ast_type_traits::DynTypedNode *>())
               delete Node;
           }
-          assert(NodeOrVector.template is<ASTContext::ParentVector *>());
 
           auto *Vector =
               NodeOrVector.template get<ASTContext::ParentVector *>();
           // Skip duplicates for types that have memoization data.
           // We must check that the type has memoization data before calling
           // std::find() because DynTypedNode::operator== can't compare all
           // types.
           bool Found = ParentStack.back().getMemoizationData() &&
private:
     ASTContext::ParentMap *Parents;
     llvm::SmallVector<ast_type_traits::DynTypedNode, 16> ParentStack;
 
     friend class RecursiveASTVisitor<ParentMapASTVisitor>;
   };
 
 } // end namespace
 
-ArrayRef<ast_type_traits::DynTypedNode>
+ASTContext::DynTypedNodeList
 ASTContext::getParents(const ast_type_traits::DynTypedNode &Node) {
   assert(Node.getMemoizationData() &&
          "Invariant broken: only nodes that support memoization may be "
          "used in the parent map.");
   if (!AllParents) {
     // We always need to run over the whole translation unit, as
     // hasAncestor can escape any subtree.
     AllParents.reset(
         ParentMapASTVisitor::buildMap(*getTranslationUnitDecl()));
   }
   ParentMap::const_iterator I = AllParents->find(Node.getMemoizationData());
   if (I == AllParents->end()) {
-    return None;
+    return llvm::ArrayRef<ast_type_traits::DynTypedNode>();
   }
-  if (auto *N = I->second.dyn_cast<ast_type_traits::DynTypedNode *>()) {
-    return llvm::makeArrayRef(N, 1);
+  if (auto *V = I->second.dyn_cast<ParentVector *>()) {
+    return llvm::makeArrayRef(*V);
   }
-  return *I->second.get<ParentVector *>();
+  return getSingleDynTypedNodeFromParentMap(I->second);
 }
 
 bool
 ASTContext::ObjCMethodsAreEqual(const ObjCMethodDecl *MethodDecl,
                                 const ObjCMethodDecl *MethodImpl) {
   // No point trying to match an unavailable/deprecated mothod.
   if (MethodDecl->hasAttr<UnavailableAttr>()
       || MethodDecl->hasAttr<DeprecatedAttr>())