bkramer created this revision.
bkramer added reviewers: klimek, djasper.
bkramer added a subscriber: cfe-commits.
Herald added a subscriber: klimek.
This relands r250831 after some fixes to shrink the ParentMap overall
with one addtional tweak: nodes with pointer identity (e.g. Decl* and
friends) can be store more efficiently so I put them in a separate map.
All other nodes (so far only TypeLoc and NNSLoc) go in a different map
keyed on DynTypedNode. This further uglifies the code but significantly
reduces memory overhead.
Overall this change still make ParentMap significantly larger but it's
nowhere as bad as before. I see about 25 MB over baseline (pre-r251008)
on X86ISelLowering.cpp. If this becomes an issue we could consider
splitting the maps further as DynTypedNode is still larger (32 bytes)
than a single TypeLoc (16 bytes) but I didn't want to introduce even
more complexity now.
http://reviews.llvm.org/D14011
Files:
include/clang/AST/ASTContext.h
include/clang/AST/ASTTypeTraits.h
include/clang/ASTMatchers/ASTMatchers.h
include/clang/ASTMatchers/ASTMatchersInternal.h
lib/AST/ASTContext.cpp
lib/ASTMatchers/ASTMatchFinder.cpp
unittests/AST/ASTContextParentMapTest.cpp
unittests/ASTMatchers/Dynamic/ParserTest.cpp
unittests/ASTMatchers/Dynamic/RegistryTest.cpp
Index: unittests/ASTMatchers/Dynamic/RegistryTest.cpp
===================================================================
--- unittests/ASTMatchers/Dynamic/RegistryTest.cpp
+++ unittests/ASTMatchers/Dynamic/RegistryTest.cpp
@@ -448,7 +448,9 @@
CompVector Comps = getCompletions();
// Overloaded
EXPECT_TRUE(hasCompletion(
- Comps, "hasParent(", "Matcher<Decl|Stmt> hasParent(Matcher<Decl|Stmt>)"));
+ Comps, "hasParent(",
+ "Matcher<TemplateArgument|NestedNameSpecifierLoc|Decl|...> "
+ "hasParent(Matcher<TemplateArgument|NestedNameSpecifierLoc|Decl|...>)"));
// Variadic.
EXPECT_TRUE(hasCompletion(Comps, "whileStmt(",
"Matcher<Stmt> whileStmt(Matcher<WhileStmt>...)"));
@@ -464,7 +466,9 @@
EXPECT_TRUE(hasCompletion(WhileComps, "hasBody(",
"Matcher<WhileStmt> hasBody(Matcher<Stmt>)"));
EXPECT_TRUE(hasCompletion(WhileComps, "hasParent(",
- "Matcher<Stmt> hasParent(Matcher<Decl|Stmt>)"));
+ "Matcher<Stmt> "
+ "hasParent(Matcher<TemplateArgument|"
+ "NestedNameSpecifierLoc|Decl|...>)"));
EXPECT_TRUE(
hasCompletion(WhileComps, "allOf(", "Matcher<T> allOf(Matcher<T>...)"));
Index: unittests/ASTMatchers/Dynamic/ParserTest.cpp
===================================================================
--- unittests/ASTMatchers/Dynamic/ParserTest.cpp
+++ unittests/ASTMatchers/Dynamic/ParserTest.cpp
@@ -318,8 +318,10 @@
Comps[1].MatcherDecl);
EXPECT_EQ("arent(", Comps[2].TypedText);
- EXPECT_EQ("Matcher<Decl> hasParent(Matcher<Decl|Stmt>)",
- Comps[2].MatcherDecl);
+ EXPECT_EQ(
+ "Matcher<Decl> "
+ "hasParent(Matcher<TemplateArgument|NestedNameSpecifierLoc|Decl|...>)",
+ Comps[2].MatcherDecl);
}
} // end anonymous namespace
Index: unittests/AST/ASTContextParentMapTest.cpp
===================================================================
--- unittests/AST/ASTContextParentMapTest.cpp
+++ unittests/AST/ASTContextParentMapTest.cpp
@@ -38,6 +38,19 @@
ifStmt(hasParent(compoundStmt()))));
}
+TEST(GetParents, ReturnsParentForTypeLoc) {
+ MatchVerifier<TypeLoc> Verifier;
+ EXPECT_TRUE(
+ Verifier.match("namespace a { class b {}; } void f(a::b) {}",
+ typeLoc(hasParent(typeLoc(hasParent(functionDecl()))))));
+}
+
+TEST(GetParents, ReturnsParentForNestedNameSpecifierLoc) {
+ MatchVerifier<NestedNameSpecifierLoc> Verifier;
+ EXPECT_TRUE(Verifier.match("namespace a { class b {}; } void f(a::b) {}",
+ nestedNameSpecifierLoc(hasParent(typeLoc()))));
+}
+
TEST(GetParents, ReturnsParentInsideTemplateInstantiations) {
MatchVerifier<Decl> DeclVerifier;
EXPECT_TRUE(DeclVerifier.match(
Index: lib/ASTMatchers/ASTMatchFinder.cpp
===================================================================
--- lib/ASTMatchers/ASTMatchFinder.cpp
+++ lib/ASTMatchers/ASTMatchFinder.cpp
@@ -621,9 +621,6 @@
if (Node.get<TranslationUnitDecl>() ==
ActiveASTContext->getTranslationUnitDecl())
return false;
- assert(Node.getMemoizationData() &&
- "Invariant broken: only nodes that support memoization may be "
- "used in the parent map.");
MatchKey Key;
Key.MatcherID = Matcher.getID();
@@ -867,7 +864,11 @@
bool MatchASTVisitor::TraverseNestedNameSpecifierLoc(
NestedNameSpecifierLoc NNS) {
+ if (!NNS)
+ return true;
+
match(NNS);
+
// We only match the nested name specifier here (as opposed to traversing it)
// because the traversal is already done in the parallel "Loc"-hierarchy.
if (NNS.hasQualifier())
Index: lib/AST/ASTContext.cpp
===================================================================
--- lib/AST/ASTContext.cpp
+++ lib/AST/ASTContext.cpp
@@ -793,8 +793,15 @@
}
void ASTContext::ReleaseParentMapEntries() {
- if (!AllParents) return;
- for (const auto &Entry : *AllParents) {
+ if (!PointerParents) return;
+ for (const auto &Entry : *PointerParents) {
+ if (Entry.second.is<ast_type_traits::DynTypedNode *>()) {
+ delete Entry.second.get<ast_type_traits::DynTypedNode *>();
+ } else if (Entry.second.is<ParentVector *>()) {
+ delete Entry.second.get<ParentVector *>();
+ }
+ }
+ for (const auto &Entry : *OtherParents) {
if (Entry.second.is<ast_type_traits::DynTypedNode *>()) {
delete Entry.second.get<ast_type_traits::DynTypedNode *>();
} else if (Entry.second.is<ParentVector *>()) {
@@ -8670,15 +8677,32 @@
namespace {
-ast_type_traits::DynTypedNode
-getSingleDynTypedNodeFromParentMap(ASTContext::ParentMap::mapped_type U) {
+ast_type_traits::DynTypedNode getSingleDynTypedNodeFromParentMap(
+ ASTContext::ParentMapPointers::mapped_type U) {
if (const auto *D = U.dyn_cast<const Decl *>())
return ast_type_traits::DynTypedNode::create(*D);
if (const auto *S = U.dyn_cast<const Stmt *>())
return ast_type_traits::DynTypedNode::create(*S);
return *U.get<ast_type_traits::DynTypedNode *>();
}
+/// Template specializations to abstract away from pointers and TypeLocs.
+/// @{
+template <typename T>
+ast_type_traits::DynTypedNode createDynTypedNode(const T &Node) {
+ return ast_type_traits::DynTypedNode::create(*Node);
+}
+template <>
+ast_type_traits::DynTypedNode createDynTypedNode(const TypeLoc &Node) {
+ return ast_type_traits::DynTypedNode::create(Node);
+}
+template <>
+ast_type_traits::DynTypedNode
+createDynTypedNode(const NestedNameSpecifierLoc &Node) {
+ return ast_type_traits::DynTypedNode::create(Node);
+}
+/// @}
+
/// \brief A \c RecursiveASTVisitor that builds a map from nodes to their
/// parents as defined by the \c RecursiveASTVisitor.
///
@@ -8693,17 +8717,21 @@
/// \brief Builds and returns the translation unit's parent map.
///
/// The caller takes ownership of the returned \c ParentMap.
- static ASTContext::ParentMap *buildMap(TranslationUnitDecl &TU) {
- ParentMapASTVisitor Visitor(new ASTContext::ParentMap);
+ static std::pair<ASTContext::ParentMapPointers *,
+ ASTContext::ParentMapOtherNodes *>
+ buildMap(TranslationUnitDecl &TU) {
+ ParentMapASTVisitor Visitor(new ASTContext::ParentMapPointers,
+ new ASTContext::ParentMapOtherNodes);
Visitor.TraverseDecl(&TU);
- return Visitor.Parents;
+ return std::make_pair(Visitor.Parents, Visitor.OtherParents);
}
private:
typedef RecursiveASTVisitor<ParentMapASTVisitor> VisitorBase;
- ParentMapASTVisitor(ASTContext::ParentMap *Parents) : Parents(Parents) {
- }
+ ParentMapASTVisitor(ASTContext::ParentMapPointers *Parents,
+ ASTContext::ParentMapOtherNodes *OtherParents)
+ : Parents(Parents), OtherParents(OtherParents) {}
bool shouldVisitTemplateInstantiations() const {
return true;
@@ -8717,8 +8745,9 @@
return false;
}
- template <typename T>
- bool TraverseNode(T *Node, bool(VisitorBase:: *traverse) (T *)) {
+ template <typename T, typename MapNodeTy, typename MapTy>
+ bool TraverseNode(T Node, MapNodeTy MapNode,
+ bool (VisitorBase::*traverse)(T), MapTy *Parents) {
if (!Node)
return true;
if (ParentStack.size() > 0) {
@@ -8732,7 +8761,7 @@
// 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];
+ auto &NodeOrVector = (*Parents)[MapNode];
if (NodeOrVector.isNull()) {
if (const auto *D = ParentStack.back().get<Decl>())
NodeOrVector = D;
@@ -8765,49 +8794,70 @@
Vector->push_back(ParentStack.back());
}
}
- ParentStack.push_back(ast_type_traits::DynTypedNode::create(*Node));
+ ParentStack.push_back(createDynTypedNode(Node));
bool Result = (this ->* traverse) (Node);
ParentStack.pop_back();
return Result;
}
bool TraverseDecl(Decl *DeclNode) {
- return TraverseNode(DeclNode, &VisitorBase::TraverseDecl);
+ return TraverseNode(DeclNode, DeclNode, &VisitorBase::TraverseDecl,
+ Parents);
}
bool TraverseStmt(Stmt *StmtNode) {
- return TraverseNode(StmtNode, &VisitorBase::TraverseStmt);
+ return TraverseNode(StmtNode, StmtNode, &VisitorBase::TraverseStmt,
+ Parents);
+ }
+
+ bool TraverseTypeLoc(TypeLoc TypeLocNode) {
+ return TraverseNode(TypeLocNode,
+ ast_type_traits::DynTypedNode::create(TypeLocNode),
+ &VisitorBase::TraverseTypeLoc, OtherParents);
}
- ASTContext::ParentMap *Parents;
+ bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) {
+ return TraverseNode(
+ NNSLocNode, ast_type_traits::DynTypedNode::create(NNSLocNode),
+ &VisitorBase::TraverseNestedNameSpecifierLoc, OtherParents);
+ }
+
+ ASTContext::ParentMapPointers *Parents;
+ ASTContext::ParentMapOtherNodes *OtherParents;
llvm::SmallVector<ast_type_traits::DynTypedNode, 16> ParentStack;
friend class RecursiveASTVisitor<ParentMapASTVisitor>;
};
} // end namespace
-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()) {
+template <typename NodeTy, typename MapTy>
+static ASTContext::DynTypedNodeList getDynNodeFromMap(const NodeTy &Node,
+ const MapTy &Map) {
+ auto I = Map.find(Node);
+ if (I == Map.end()) {
return llvm::ArrayRef<ast_type_traits::DynTypedNode>();
}
- if (auto *V = I->second.dyn_cast<ParentVector *>()) {
+ if (auto *V = I->second.template dyn_cast<ASTContext::ParentVector *>()) {
return llvm::makeArrayRef(*V);
}
return getSingleDynTypedNodeFromParentMap(I->second);
}
+ASTContext::DynTypedNodeList
+ASTContext::getParents(const ast_type_traits::DynTypedNode &Node) {
+ if (!PointerParents) {
+ // We always need to run over the whole translation unit, as
+ // hasAncestor can escape any subtree.
+ auto Maps = ParentMapASTVisitor::buildMap(*getTranslationUnitDecl());
+ PointerParents.reset(Maps.first);
+ OtherParents.reset(Maps.second);
+ }
+ if (Node.getNodeKind().hasPointerIdentity())
+ return getDynNodeFromMap(Node.getMemoizationData(), *PointerParents);
+ return getDynNodeFromMap(Node, *OtherParents);
+}
+
bool
ASTContext::ObjCMethodsAreEqual(const ObjCMethodDecl *MethodDecl,
const ObjCMethodDecl *MethodImpl) {
Index: include/clang/ASTMatchers/ASTMatchersInternal.h
===================================================================
--- include/clang/ASTMatchers/ASTMatchersInternal.h
+++ include/clang/ASTMatchers/ASTMatchersInternal.h
@@ -848,8 +848,10 @@
BoundNodesTreeBuilder *Builder,
AncestorMatchMode MatchMode) {
static_assert(std::is_base_of<Decl, T>::value ||
- std::is_base_of<Stmt, T>::value,
- "only Decl or Stmt allowed for recursive matching");
+ std::is_base_of<NestedNameSpecifierLoc, T>::value ||
+ std::is_base_of<Stmt, T>::value ||
+ std::is_base_of<TypeLoc, T>::value,
+ "type not allowed for recursive matching");
return matchesAncestorOf(ast_type_traits::DynTypedNode::create(Node),
Matcher, Builder, MatchMode);
}
Index: include/clang/ASTMatchers/ASTMatchers.h
===================================================================
--- include/clang/ASTMatchers/ASTMatchers.h
+++ include/clang/ASTMatchers/ASTMatchers.h
@@ -2068,8 +2068,10 @@
///
/// Usable as: Any Matcher
const internal::ArgumentAdaptingMatcherFunc<
- internal::HasParentMatcher, internal::TypeList<Decl, Stmt>,
- internal::TypeList<Decl, Stmt> > LLVM_ATTRIBUTE_UNUSED hasParent = {};
+ internal::HasParentMatcher,
+ internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>,
+ internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>>
+ LLVM_ATTRIBUTE_UNUSED hasParent = {};
/// \brief Matches AST nodes that have an ancestor that matches the provided
/// matcher.
@@ -2083,8 +2085,10 @@
///
/// Usable as: Any Matcher
const internal::ArgumentAdaptingMatcherFunc<
- internal::HasAncestorMatcher, internal::TypeList<Decl, Stmt>,
- internal::TypeList<Decl, Stmt> > LLVM_ATTRIBUTE_UNUSED hasAncestor = {};
+ internal::HasAncestorMatcher,
+ internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>,
+ internal::TypeList<Decl, NestedNameSpecifierLoc, Stmt, TypeLoc>>
+ LLVM_ATTRIBUTE_UNUSED hasAncestor = {};
/// \brief Matches if the provided matcher does not match.
///
Index: include/clang/AST/ASTTypeTraits.h
===================================================================
--- include/clang/AST/ASTTypeTraits.h
+++ include/clang/AST/ASTTypeTraits.h
@@ -268,6 +268,28 @@
/// FIXME: Implement comparsion for other node types (currently
/// only Stmt, Decl, Type and NestedNameSpecifier return memoization data).
bool operator<(const DynTypedNode &Other) const {
+ if (!NodeKind.isSame(Other.NodeKind))
+ return NodeKind < Other.NodeKind;
+
+ if (ASTNodeKind::getFromNodeKind<TypeLoc>().isSame(NodeKind)) {
+ auto TLA = getUnchecked<TypeLoc>();
+ auto TLB = Other.getUnchecked<TypeLoc>();
+ return std::make_pair(TLA.getType().getAsOpaquePtr(),
+ TLA.getOpaqueData()) <
+ std::make_pair(TLB.getType().getAsOpaquePtr(),
+ TLB.getOpaqueData());
+ }
+
+ if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(
+ NodeKind)) {
+ auto NNSLA = getUnchecked<NestedNameSpecifierLoc>();
+ auto NNSLB = Other.getUnchecked<NestedNameSpecifierLoc>();
+ return std::make_pair(NNSLA.getNestedNameSpecifier(),
+ NNSLA.getOpaqueData()) <
+ std::make_pair(NNSLB.getNestedNameSpecifier(),
+ NNSLB.getOpaqueData());
+ }
+
assert(getMemoizationData() && Other.getMemoizationData());
return getMemoizationData() < Other.getMemoizationData();
}
@@ -281,14 +303,62 @@
if (ASTNodeKind::getFromNodeKind<QualType>().isSame(NodeKind))
return getUnchecked<QualType>() == Other.getUnchecked<QualType>();
+ if (ASTNodeKind::getFromNodeKind<TypeLoc>().isSame(NodeKind))
+ return getUnchecked<TypeLoc>() == Other.getUnchecked<TypeLoc>();
+
+ if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(NodeKind))
+ return getUnchecked<NestedNameSpecifierLoc>() ==
+ Other.getUnchecked<NestedNameSpecifierLoc>();
+
assert(getMemoizationData() && Other.getMemoizationData());
return getMemoizationData() == Other.getMemoizationData();
}
bool operator!=(const DynTypedNode &Other) const {
return !operator==(Other);
}
/// @}
+ /// \brief Hooks for using DynTypedNode as a key in a DenseMap.
+ struct DenseMapInfo {
+ static inline DynTypedNode getEmptyKey() {
+ DynTypedNode Node;
+ Node.NodeKind = ASTNodeKind::DenseMapInfo::getEmptyKey();
+ return Node;
+ }
+ static inline DynTypedNode getTombstoneKey() {
+ DynTypedNode Node;
+ Node.NodeKind = ASTNodeKind::DenseMapInfo::getTombstoneKey();
+ return Node;
+ }
+ static unsigned getHashValue(const DynTypedNode &Val) {
+ // FIXME: Add hashing support for the remaining types.
+ if (ASTNodeKind::getFromNodeKind<TypeLoc>().isSame(Val.NodeKind)) {
+ auto TL = Val.getUnchecked<TypeLoc>();
+ return llvm::hash_combine(TL.getType().getAsOpaquePtr(),
+ TL.getOpaqueData());
+ }
+
+ if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(
+ Val.NodeKind)) {
+ auto NNSL = Val.getUnchecked<NestedNameSpecifierLoc>();
+ return llvm::hash_combine(NNSL.getNestedNameSpecifier(),
+ NNSL.getOpaqueData());
+ }
+
+ assert(Val.getMemoizationData());
+ return llvm::hash_value(Val.getMemoizationData());
+ }
+ static bool isEqual(const DynTypedNode &LHS, const DynTypedNode &RHS) {
+ auto Empty = ASTNodeKind::DenseMapInfo::getEmptyKey();
+ auto TombStone = ASTNodeKind::DenseMapInfo::getTombstoneKey();
+ return (ASTNodeKind::DenseMapInfo::isEqual(LHS.NodeKind, Empty) &&
+ ASTNodeKind::DenseMapInfo::isEqual(RHS.NodeKind, Empty)) ||
+ (ASTNodeKind::DenseMapInfo::isEqual(LHS.NodeKind, TombStone) &&
+ ASTNodeKind::DenseMapInfo::isEqual(RHS.NodeKind, TombStone)) ||
+ LHS == RHS;
+ }
+ };
+
private:
/// \brief Takes care of converting from and to \c T.
template <typename T, typename EnablerT = void> struct BaseConverter;
@@ -426,6 +496,10 @@
struct DenseMapInfo<clang::ast_type_traits::ASTNodeKind>
: clang::ast_type_traits::ASTNodeKind::DenseMapInfo {};
+template <>
+struct DenseMapInfo<clang::ast_type_traits::DynTypedNode>
+ : clang::ast_type_traits::DynTypedNode::DenseMapInfo {};
+
} // end namespace llvm
#endif
Index: include/clang/AST/ASTContext.h
===================================================================
--- include/clang/AST/ASTContext.h
+++ include/clang/AST/ASTContext.h
@@ -451,11 +451,21 @@
/// \brief Contains parents of a node.
typedef llvm::SmallVector<ast_type_traits::DynTypedNode, 2> ParentVector;
- /// \brief Maps from a node to its parents.
+ /// \brief Maps from a node to its parents. This is used for nodes that have
+ /// pointer identity only, which are more common and we can save space by
+ /// only storing an unique pointer to them.
typedef llvm::DenseMap<const void *,
llvm::PointerUnion4<const Decl *, const Stmt *,
ast_type_traits::DynTypedNode *,
- ParentVector *>> ParentMap;
+ ParentVector *>> ParentMapPointers;
+
+ /// Parent map for nodes without pointer identity. We store a full
+ /// DynTypedNode for all keys.
+ typedef llvm::DenseMap<
+ ast_type_traits::DynTypedNode,
+ llvm::PointerUnion4<const Decl *, const Stmt *,
+ ast_type_traits::DynTypedNode *, ParentVector *>>
+ ParentMapOtherNodes;
/// Container for either a single DynTypedNode or for an ArrayRef to
/// DynTypedNode. For use with ParentMap.
@@ -2513,7 +2523,8 @@
void ReleaseDeclContextMaps();
void ReleaseParentMapEntries();
- std::unique_ptr<ParentMap> AllParents;
+ std::unique_ptr<ParentMapPointers> PointerParents;
+ std::unique_ptr<ParentMapOtherNodes> OtherParents;
std::unique_ptr<VTableContextBase> VTContext;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
