Re: [PATCH] D13976: [AST] Store Decl* and Stmt* directly into the ParentMap.

2015-10-22 Thread Manuel Klimek via cfe-commits 
klimek accepted this revision.
klimek added a comment.
This revision is now accepted and ready to land.

lg



Comment at: include/clang/AST/ASTContext.h:463
@@ +462,3 @@
+  class DynTypedNodeList {
+typedef ast_type_traits::DynTypedNode DynTypedNode;
+typedef ArrayRef ARef;

I think "using" is clearer.


Comment at: include/clang/AST/ASTContext.h:464
@@ +463,3 @@
+typedef ast_type_traits::DynTypedNode DynTypedNode;
+typedef ArrayRef ARef;
+llvm::AlignedCharArrayUnion Storage;

Show me what ArrayRef looks like written out below :)


http://reviews.llvm.org/D13976



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

Re: [PATCH] D13976: [AST] Store Decl* and Stmt* directly into the ParentMap.

2015-10-22 Thread Phabricator via cfe-commits 
This revision was automatically updated to reflect the committed changes.
Closed by commit rL251008: [AST] Store Decl* and Stmt* directly into the 
ParentMap. (authored by d0k).

Changed prior to commit:
  http://reviews.llvm.org/D13976?vs=38105=38110#toc

Repository:
  rL LLVM

http://reviews.llvm.org/D13976

Files:
  cfe/trunk/include/clang/AST/ASTContext.h
  cfe/trunk/lib/AST/ASTContext.cpp

Index: cfe/trunk/lib/AST/ASTContext.cpp
===
--- cfe/trunk/lib/AST/ASTContext.cpp
+++ cfe/trunk/lib/AST/ASTContext.cpp
@@ -797,8 +797,7 @@
   for (const auto  : *AllParents) {
 if (Entry.second.is()) {
   delete Entry.second.get();
-} else {
-  assert(Entry.second.is());
+} else if (Entry.second.is()) {
   delete Entry.second.get();
 }
   }
@@ -8673,6 +8672,15 @@
 
 namespace {
 
+ast_type_traits::DynTypedNode
+getSingleDynTypedNodeFromParentMap(ASTContext::ParentMap::mapped_type U) {
+  if (const auto *D = U.template dyn_cast())
+return ast_type_traits::DynTypedNode::create(*D);
+  if (const auto *S = U.template dyn_cast())
+return ast_type_traits::DynTypedNode::create(*S);
+  return *U.template get();
+}
+
   /// \brief A \c RecursiveASTVisitor that builds a map from nodes to their
   /// parents as defined by the \c RecursiveASTVisitor.
   ///
@@ -8728,16 +8736,23 @@
 // do not have pointer identity.
 auto  = (*Parents)[Node];
 if (NodeOrVector.isNull()) {
-  NodeOrVector = new ast_type_traits::DynTypedNode(ParentStack.back());
+  if (const auto *D = ParentStack.back().get())
+NodeOrVector = D;
+  else if (const auto *S = ParentStack.back().get())
+NodeOrVector = S;
+  else
+NodeOrVector =
+new ast_type_traits::DynTypedNode(ParentStack.back());
 } else {
-  if (NodeOrVector.template is()) {
-auto *Node =
-NodeOrVector.template get();
-auto *Vector = new ASTContext::ParentVector(1, *Node);
+  if (!NodeOrVector.template is()) {
+auto *Vector = new ASTContext::ParentVector(
+1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
 NodeOrVector = Vector;
-delete Node;
+if (auto *Node =
+NodeOrVector
+.template dyn_cast())
+  delete Node;
   }
-  assert(NodeOrVector.template is());
 
   auto *Vector =
   NodeOrVector.template get();
@@ -8774,7 +8789,7 @@
 
 } // end namespace
 
-ArrayRef
+ASTContext::DynTypedNodeList
 ASTContext::getParents(const ast_type_traits::DynTypedNode ) {
   assert(Node.getMemoizationData() &&
  "Invariant broken: only nodes that support memoization may be "
@@ -8787,12 +8802,12 @@
   }
   ParentMap::const_iterator I = AllParents->find(Node.getMemoizationData());
   if (I == AllParents->end()) {
-return None;
+return llvm::ArrayRef();
   }
-  if (auto *N = I->second.dyn_cast()) {
-return llvm::makeArrayRef(N, 1);
+  if (auto *V = I->second.dyn_cast()) {
+return llvm::makeArrayRef(*V);
   }
-  return *I->second.get();
+  return getSingleDynTypedNodeFromParentMap(I->second);
 }
 
 bool
Index: cfe/trunk/include/clang/AST/ASTContext.h
===
--- cfe/trunk/include/clang/AST/ASTContext.h
+++ cfe/trunk/include/clang/AST/ASTContext.h
@@ -453,8 +453,47 @@
 
   /// \brief Maps from a node to its parents.
   typedef llvm::DenseMap> ParentMap;
+ llvm::PointerUnion4> 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;
+llvm::AlignedCharArrayUnion Storage;
+bool IsSingleNode;
+
+  public:
+DynTypedNodeList(const DynTypedNode ) : IsSingleNode(true) {
+  new (Storage.buffer) DynTypedNode(N);
+}
+DynTypedNodeList(ArrayRef A) : IsSingleNode(false) {
+  new (Storage.buffer) ArrayRef(A);
+}
+
+const ast_type_traits::DynTypedNode *begin() const {
+  if (!IsSingleNode)
+return reinterpret_cast *>(Storage.buffer)
+->begin();
+  return reinterpret_cast(Storage.buffer);
+}
+
+const ast_type_traits::DynTypedNode *end() const {
+  if (!IsSingleNode)
+return reinterpret_cast *>(Storage.buffer)
+->end();
+  return reinterpret_cast(Storage.buffer) + 1;
+}
+
+size_t size() const { return end() - begin(); }
+bool empty() const { return begin() == end(); }
+const DynTypedNode [](size_t N) const {
+  assert(N < size() && "Out of bounds!");
+  return *(begin() + N);
+}
+  };
 
   /// \brief Returns the parents of the given node.
   ///
@@

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

2015-10-22 Thread Benjamin Kramer via cfe-commits 
bkramer created this revision.
bkramer added reviewers: klimek, djasper.
bkramer added a subscriber: cfe-commits.

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.

http://reviews.llvm.org/D13976

Files:
  include/clang/AST/ASTContext.h
  lib/AST/ASTContext.cpp

Index: lib/AST/ASTContext.cpp
===
--- lib/AST/ASTContext.cpp
+++ lib/AST/ASTContext.cpp
@@ -797,8 +797,7 @@
   for (const auto  : *AllParents) {
 if (Entry.second.is()) {
   delete Entry.second.get();
-} else {
-  assert(Entry.second.is());
+} else if (Entry.second.is()) {
   delete Entry.second.get();
 }
   }
@@ -8673,6 +8672,15 @@
 
 namespace {
 
+ast_type_traits::DynTypedNode
+getSingleDynTypedNodeFromParentMap(ASTContext::ParentMap::mapped_type U) {
+  if (const auto *D = U.template dyn_cast())
+return ast_type_traits::DynTypedNode::create(*D);
+  if (const auto *S = U.template dyn_cast())
+return ast_type_traits::DynTypedNode::create(*S);
+  return *U.template get();
+}
+
   /// \brief A \c RecursiveASTVisitor that builds a map from nodes to their
   /// parents as defined by the \c RecursiveASTVisitor.
   ///
@@ -8728,16 +8736,23 @@
 // do not have pointer identity.
 auto  = (*Parents)[Node];
 if (NodeOrVector.isNull()) {
-  NodeOrVector = new ast_type_traits::DynTypedNode(ParentStack.back());
+  if (const auto *D = ParentStack.back().get())
+NodeOrVector = D;
+  else if (const auto *S = ParentStack.back().get())
+NodeOrVector = S;
+  else
+NodeOrVector =
+new ast_type_traits::DynTypedNode(ParentStack.back());
 } else {
-  if (NodeOrVector.template is()) {
-auto *Node =
-NodeOrVector.template get();
-auto *Vector = new ASTContext::ParentVector(1, *Node);
+  if (!NodeOrVector.template is()) {
+auto *Vector = new ASTContext::ParentVector(
+1, getSingleDynTypedNodeFromParentMap(NodeOrVector));
 NodeOrVector = Vector;
-delete Node;
+if (auto *Node =
+NodeOrVector
+.template dyn_cast())
+  delete Node;
   }
-  assert(NodeOrVector.template is());
 
   auto *Vector =
   NodeOrVector.template get();
@@ -8774,7 +8789,7 @@
 
 } // end namespace
 
-ArrayRef
+ASTContext::DynTypedNodeList
 ASTContext::getParents(const ast_type_traits::DynTypedNode ) {
   assert(Node.getMemoizationData() &&
  "Invariant broken: only nodes that support memoization may be "
@@ -8787,12 +8802,12 @@
   }
   ParentMap::const_iterator I = AllParents->find(Node.getMemoizationData());
   if (I == AllParents->end()) {
-return None;
+return llvm::ArrayRef();
   }
-  if (auto *N = I->second.dyn_cast()) {
-return llvm::makeArrayRef(N, 1);
+  if (auto *V = I->second.dyn_cast()) {
+return llvm::makeArrayRef(*V);
   }
-  return *I->second.get();
+  return getSingleDynTypedNodeFromParentMap(I->second);
 }
 
 bool
Index: include/clang/AST/ASTContext.h
===
--- include/clang/AST/ASTContext.h
+++ include/clang/AST/ASTContext.h
@@ -453,8 +453,45 @@
 
   /// \brief Maps from a node to its parents.
   typedef llvm::DenseMap> ParentMap;
+ llvm::PointerUnion4> 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 ARef;
+llvm::AlignedCharArrayUnion Storage;
+bool IsSingleNode;
+
+  public:
+DynTypedNodeList(const DynTypedNode ) : 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(Storage.buffer)->begin();
+  return reinterpret_cast(Storage.buffer);
+}
+
+const ast_type_traits::DynTypedNode *end() const {
+  if (!IsSingleNode)
+return reinterpret_cast(Storage.buffer)->end();
+  return reinterpret_cast(Storage.buffer) + 1;
+}
+
+size_t size() const { return end()