Skip to content

Commit 8a81daa

Browse files
rnkrnk
committed
[AST] Split parent map traversal logic into ParentMapContext.h
The only part of ASTContext.h that requires most AST types to be complete is the parent map. Nothing in Clang proper uses the ParentMap, so split it out into its own class. Make ASTContext own the ParentMapContext so there is still a one-to-one relationship. After this change, 562 fewer files depend on ASTTypeTraits.h, and 66 fewer depend on TypeLoc.h: $ diff -u deps-before.txt deps-after.txt | \ grep '^[-+] ' | sort | uniq -c | sort -nr | less 562 - ../clang/include/clang/AST/ASTTypeTraits.h 340 + ../clang/include/clang/AST/ParentMapContext.h 66 - ../clang/include/clang/AST/TypeLocNodes.def 66 - ../clang/include/clang/AST/TypeLoc.h 15 - ../clang/include/clang/AST/TemplateBase.h ... I computed deps-before.txt and deps-after.txt with `ninja -t deps`. This removes a common and key dependency on TemplateBase.h and TypeLoc.h. This also has the effect of breaking the ParentMap RecursiveASTVisitor instantiation into its own file, which roughly halves the compilation time of ASTContext.cpp (29.75s -> 17.66s). The new file takes 13.8s to compile. I left behind forwarding methods for getParents(), but clients will need to include a new header to make them work: #include "clang/AST/ParentMapContext.h" I noticed that this parent map functionality is unfortunately duplicated in ParentMap.h, which only works for Stmt nodes. Reviewed By: rsmith Differential Revision: https://reviews.llvm.org/D71313
1 parent b1f3a0f commit 8a81daa

File tree

18 files changed

+465
-350
lines changed

18 files changed

+465
-350
lines changed

‎clang-tools-extra/clang-tidy/cppcoreguidelines/ProBoundsArrayToPointerDecayCheck.cpp

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@
88

99
#include "ProBoundsArrayToPointerDecayCheck.h"
1010
#include "clang/AST/ASTContext.h"
11+
#include "clang/AST/ParentMapContext.h"
1112
#include "clang/ASTMatchers/ASTMatchFinder.h"
1213

1314
using namespace clang::ast_matchers;
@@ -35,8 +36,7 @@ AST_MATCHER_P(Expr, hasParentIgnoringImpCasts,
3536
ast_matchers::internal::Matcher<Expr>, InnerMatcher) {
3637
const Expr *E = &Node;
3738
do {
38-
ASTContext::DynTypedNodeList Parents =
39-
Finder->getASTContext().getParents(*E);
39+
DynTypedNodeList Parents = Finder->getASTContext().getParents(*E);
4040
if (Parents.size() != 1)
4141
return false;
4242
E = Parents[0].get<Expr>();

‎clang-tools-extra/clang-tidy/readability/MakeMemberFunctionConstCheck.cpp

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@
88

99
#include "MakeMemberFunctionConstCheck.h"
1010
#include "clang/AST/ASTContext.h"
11+
#include "clang/AST/ParentMapContext.h"
1112
#include "clang/AST/RecursiveASTVisitor.h"
1213
#include "clang/ASTMatchers/ASTMatchFinder.h"
1314

@@ -57,7 +58,7 @@ class FindUsageOfThis : public RecursiveASTVisitor<FindUsageOfThis> {
5758
UsageKind Usage = Unused;
5859

5960
template <class T> const T *getParent(const Expr *E) {
60-
ASTContext::DynTypedNodeList Parents = Ctxt.getParents(*E);
61+
DynTypedNodeList Parents = Ctxt.getParents(*E);
6162
if (Parents.size() != 1)
6263
return nullptr;
6364

‎clang-tools-extra/clang-tidy/utils/ExprSequence.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@ static SmallVector<const Stmt *, 1> getParentStmts(const Stmt *S,
2828
ASTContext *Context) {
2929
SmallVector<const Stmt *, 1> Result;
3030

31-
ASTContext::DynTypedNodeList Parents = Context->getParents(*S);
31+
DynTypedNodeList Parents = Context->getParents(*S);
3232

3333
SmallVector<ast_type_traits::DynTypedNode, 1> NodesToProcess(Parents.begin(),
3434
Parents.end());

‎clang/include/clang/AST/ASTContext.h

Lines changed: 13 additions & 99 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@
1515
#define LLVM_CLANG_AST_ASTCONTEXT_H
1616

1717
#include "clang/AST/ASTContextAllocate.h"
18-
#include "clang/AST/ASTTypeTraits.h"
18+
#include "clang/AST/ASTFwd.h"
1919
#include "clang/AST/CanonicalType.h"
2020
#include "clang/AST/CommentCommandTraits.h"
2121
#include "clang/AST/ComparisonCategories.h"
@@ -26,7 +26,6 @@
2626
#include "clang/AST/NestedNameSpecifier.h"
2727
#include "clang/AST/PrettyPrinter.h"
2828
#include "clang/AST/RawCommentList.h"
29-
#include "clang/AST/TemplateBase.h"
3029
#include "clang/AST/TemplateName.h"
3130
#include "clang/AST/Type.h"
3231
#include "clang/Basic/AddressSpaces.h"
@@ -94,6 +93,8 @@ class CXXConstructorDecl;
9493
class CXXMethodDecl;
9594
class CXXRecordDecl;
9695
class DiagnosticsEngine;
96+
class ParentMapContext;
97+
class DynTypedNodeList;
9798
class Expr;
9899
class FixedPointSemantics;
99100
class GlobalDecl;
@@ -129,6 +130,10 @@ class VarTemplateDecl;
129130
class VTableContextBase;
130131
struct BlockVarCopyInit;
131132

133+
namespace ast_type_traits {
134+
class DynTypedNode;
135+
}
136+
132137
namespace Builtin {
133138

134139
class Context;
@@ -565,18 +570,9 @@ class ASTContext : public RefCountedBase<ASTContext> {
565570
const TargetInfo *AuxTarget = nullptr;
566571
clang::PrintingPolicy PrintingPolicy;
567572
std::unique_ptr<interp::Context> InterpContext;
568-
569-
ast_type_traits::TraversalKind Traversal = ast_type_traits::TK_AsIs;
573+
std::unique_ptr<ParentMapContext> ParentMapCtx;
570574

571575
public:
572-
ast_type_traits::TraversalKind getTraversalKind() const { return Traversal; }
573-
void setTraversalKind(ast_type_traits::TraversalKind TK) { Traversal = TK; }
574-
575-
const Expr *traverseIgnored(const Expr *E) const;
576-
Expr *traverseIgnored(Expr *E) const;
577-
ast_type_traits::DynTypedNode
578-
traverseIgnored(const ast_type_traits::DynTypedNode &N) const;
579-
580576
IdentifierTable &Idents;
581577
SelectorTable &Selectors;
582578
Builtin::Context &BuiltinInfo;
@@ -587,46 +583,8 @@ class ASTContext : public RefCountedBase<ASTContext> {
587583
/// Returns the clang bytecode interpreter context.
588584
interp::Context &getInterpContext();
589585

590-
/// Container for either a single DynTypedNode or for an ArrayRef to
591-
/// DynTypedNode. For use with ParentMap.
592-
class DynTypedNodeList {
593-
using DynTypedNode = ast_type_traits::DynTypedNode;
594-
595-
llvm::AlignedCharArrayUnion<ast_type_traits::DynTypedNode,
596-
ArrayRef<DynTypedNode>> Storage;
597-
bool IsSingleNode;
598-
599-
public:
600-
DynTypedNodeList(const DynTypedNode &N) : IsSingleNode(true) {
601-
new (Storage.buffer) DynTypedNode(N);
602-
}
603-
604-
DynTypedNodeList(ArrayRef<DynTypedNode> A) : IsSingleNode(false) {
605-
new (Storage.buffer) ArrayRef<DynTypedNode>(A);
606-
}
607-
608-
const ast_type_traits::DynTypedNode *begin() const {
609-
if (!IsSingleNode)
610-
return reinterpret_cast<const ArrayRef<DynTypedNode> *>(Storage.buffer)
611-
->begin();
612-
return reinterpret_cast<const DynTypedNode *>(Storage.buffer);
613-
}
614-
615-
const ast_type_traits::DynTypedNode *end() const {
616-
if (!IsSingleNode)
617-
return reinterpret_cast<const ArrayRef<DynTypedNode> *>(Storage.buffer)
618-
->end();
619-
return reinterpret_cast<const DynTypedNode *>(Storage.buffer) + 1;
620-
}
621-
622-
size_t size() const { return end() - begin(); }
623-
bool empty() const { return begin() == end(); }
624-
625-
const DynTypedNode &operator[](size_t N) const {
626-
assert(N < size() && "Out of bounds!");
627-
return *(begin() + N);
628-
}
629-
};
586+
/// Returns the dynamic AST node parent map context.
587+
ParentMapContext &getParentMapContext();
630588

631589
// A traversal scope limits the parts of the AST visible to certain analyses.
632590
// RecursiveASTVisitor::TraverseAST will only visit reachable nodes, and
@@ -638,35 +596,9 @@ class ASTContext : public RefCountedBase<ASTContext> {
638596
std::vector<Decl *> getTraversalScope() const { return TraversalScope; }
639597
void setTraversalScope(const std::vector<Decl *> &);
640598

641-
/// Returns the parents of the given node (within the traversal scope).
642-
///
643-
/// Note that this will lazily compute the parents of all nodes
644-
/// and store them for later retrieval. Thus, the first call is O(n)
645-
/// in the number of AST nodes.
646-
///
647-
/// Caveats and FIXMEs:
648-
/// Calculating the parent map over all AST nodes will need to load the
649-
/// full AST. This can be undesirable in the case where the full AST is
650-
/// expensive to create (for example, when using precompiled header
651-
/// preambles). Thus, there are good opportunities for optimization here.
652-
/// One idea is to walk the given node downwards, looking for references
653-
/// to declaration contexts - once a declaration context is found, compute
654-
/// the parent map for the declaration context; if that can satisfy the
655-
/// request, loading the whole AST can be avoided. Note that this is made
656-
/// more complex by statements in templates having multiple parents - those
657-
/// problems can be solved by building closure over the templated parts of
658-
/// the AST, which also avoids touching large parts of the AST.
659-
/// Additionally, we will want to add an interface to already give a hint
660-
/// where to search for the parents, for example when looking at a statement
661-
/// inside a certain function.
662-
///
663-
/// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc,
664-
/// NestedNameSpecifier or NestedNameSpecifierLoc.
665-
template <typename NodeT> DynTypedNodeList getParents(const NodeT &Node) {
666-
return getParents(ast_type_traits::DynTypedNode::create(Node));
667-
}
668-
669-
DynTypedNodeList getParents(const ast_type_traits::DynTypedNode &Node);
599+
/// Forwards to get node parents from the ParentMapContext. New callers should
600+
/// use ParentMapContext::getParents() directly.
601+
template <typename NodeT> DynTypedNodeList getParents(const NodeT &Node);
670602

671603
const clang::PrintingPolicy &getPrintingPolicy() const {
672604
return PrintingPolicy;
@@ -3026,8 +2958,6 @@ OPT_LIST(V)
30262958
llvm::PointerIntPair<StoredDeclsMap *, 1> LastSDM;
30272959

30282960
std::vector<Decl *> TraversalScope;
3029-
class ParentMap;
3030-
std::map<ast_type_traits::TraversalKind, std::unique_ptr<ParentMap>> Parents;
30312961

30322962
std::unique_ptr<VTableContextBase> VTContext;
30332963

@@ -3071,22 +3001,6 @@ inline Selector GetUnarySelector(StringRef name, ASTContext &Ctx) {
30713001
return Ctx.Selectors.getSelector(1, &II);
30723002
}
30733003

3074-
class TraversalKindScope {
3075-
ASTContext &Ctx;
3076-
ast_type_traits::TraversalKind TK = ast_type_traits::TK_AsIs;
3077-
3078-
public:
3079-
TraversalKindScope(ASTContext &Ctx,
3080-
llvm::Optional<ast_type_traits::TraversalKind> ScopeTK)
3081-
: Ctx(Ctx) {
3082-
TK = Ctx.getTraversalKind();
3083-
if (ScopeTK)
3084-
Ctx.setTraversalKind(*ScopeTK);
3085-
}
3086-
3087-
~TraversalKindScope() { Ctx.setTraversalKind(TK); }
3088-
};
3089-
30903004
} // namespace clang
30913005

30923006
// operator new and delete aren't allowed inside namespaces.

‎clang/include/clang/AST/ASTNodeTraverser.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,7 @@
1515
#ifndef LLVM_CLANG_AST_ASTNODETRAVERSER_H
1616
#define LLVM_CLANG_AST_ASTNODETRAVERSER_H
1717

18+
#include "clang/AST/ASTTypeTraits.h"
1819
#include "clang/AST/AttrVisitor.h"
1920
#include "clang/AST/CommentVisitor.h"
2021
#include "clang/AST/DeclVisitor.h"

‎clang/include/clang/AST/ParentMapContext.h

Lines changed: 150 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,150 @@
1+
//===- ParentMapContext.h - Map of parents using DynTypedNode -------*- C++ -*-===//
2+
//
3+
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4+
// See https://llvm.org/LICENSE.txt for license information.
5+
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6+
//
7+
//===----------------------------------------------------------------------===//
8+
//
9+
// Similar to ParentMap.h, but generalizes to non-Stmt nodes, which can have
10+
// multiple parents.
11+
//
12+
//===----------------------------------------------------------------------===//
13+
14+
#ifndef LLVM_CLANG_AST_PARENTMAPCONTEXT_H
15+
#define LLVM_CLANG_AST_PARENTMAPCONTEXT_H
16+
17+
#include "clang/AST/ASTContext.h"
18+
#include "clang/AST/ASTTypeTraits.h"
19+
20+
namespace clang {
21+
class DynTypedNodeList;
22+
23+
class ParentMapContext {
24+
public:
25+
ParentMapContext(ASTContext &Ctx);
26+
27+
~ParentMapContext();
28+
29+
/// Returns the parents of the given node (within the traversal scope).
30+
///
31+
/// Note that this will lazily compute the parents of all nodes
32+
/// and store them for later retrieval. Thus, the first call is O(n)
33+
/// in the number of AST nodes.
34+
///
35+
/// Caveats and FIXMEs:
36+
/// Calculating the parent map over all AST nodes will need to load the
37+
/// full AST. This can be undesirable in the case where the full AST is
38+
/// expensive to create (for example, when using precompiled header
39+
/// preambles). Thus, there are good opportunities for optimization here.
40+
/// One idea is to walk the given node downwards, looking for references
41+
/// to declaration contexts - once a declaration context is found, compute
42+
/// the parent map for the declaration context; if that can satisfy the
43+
/// request, loading the whole AST can be avoided. Note that this is made
44+
/// more complex by statements in templates having multiple parents - those
45+
/// problems can be solved by building closure over the templated parts of
46+
/// the AST, which also avoids touching large parts of the AST.
47+
/// Additionally, we will want to add an interface to already give a hint
48+
/// where to search for the parents, for example when looking at a statement
49+
/// inside a certain function.
50+
///
51+
/// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc,
52+
/// NestedNameSpecifier or NestedNameSpecifierLoc.
53+
template <typename NodeT> DynTypedNodeList getParents(const NodeT &Node);
54+
55+
DynTypedNodeList getParents(const ast_type_traits::DynTypedNode &Node);
56+
57+
/// Clear parent maps.
58+
void clear();
59+
60+
ast_type_traits::TraversalKind getTraversalKind() const { return Traversal; }
61+
void setTraversalKind(ast_type_traits::TraversalKind TK) { Traversal = TK; }
62+
63+
const Expr *traverseIgnored(const Expr *E) const;
64+
Expr *traverseIgnored(Expr *E) const;
65+
ast_type_traits::DynTypedNode
66+
traverseIgnored(const ast_type_traits::DynTypedNode &N) const;
67+
68+
private:
69+
ASTContext &ASTCtx;
70+
class ParentMap;
71+
ast_type_traits::TraversalKind Traversal = ast_type_traits::TK_AsIs;
72+
std::map<ast_type_traits::TraversalKind, std::unique_ptr<ParentMap>> Parents;
73+
};
74+
75+
class TraversalKindScope {
76+
ParentMapContext &Ctx;
77+
ast_type_traits::TraversalKind TK = ast_type_traits::TK_AsIs;
78+
79+
public:
80+
TraversalKindScope(ASTContext &ASTCtx,
81+
llvm::Optional<ast_type_traits::TraversalKind> ScopeTK)
82+
: Ctx(ASTCtx.getParentMapContext()) {
83+
TK = Ctx.getTraversalKind();
84+
if (ScopeTK)
85+
Ctx.setTraversalKind(*ScopeTK);
86+
}
87+
88+
~TraversalKindScope() { Ctx.setTraversalKind(TK); }
89+
};
90+
91+
/// Container for either a single DynTypedNode or for an ArrayRef to
92+
/// DynTypedNode. For use with ParentMap.
93+
class DynTypedNodeList {
94+
using DynTypedNode = ast_type_traits::DynTypedNode;
95+
96+
llvm::AlignedCharArrayUnion<ast_type_traits::DynTypedNode,
97+
ArrayRef<DynTypedNode>> Storage;
98+
bool IsSingleNode;
99+
100+
public:
101+
DynTypedNodeList(const DynTypedNode &N) : IsSingleNode(true) {
102+
new (Storage.buffer) DynTypedNode(N);
103+
}
104+
105+
DynTypedNodeList(ArrayRef<DynTypedNode> A) : IsSingleNode(false) {
106+
new (Storage.buffer) ArrayRef<DynTypedNode>(A);
107+
}
108+
109+
const ast_type_traits::DynTypedNode *begin() const {
110+
if (!IsSingleNode)
111+
return reinterpret_cast<const ArrayRef<DynTypedNode> *>(Storage.buffer)
112+
->begin();
113+
return reinterpret_cast<const DynTypedNode *>(Storage.buffer);
114+
}
115+
116+
const ast_type_traits::DynTypedNode *end() const {
117+
if (!IsSingleNode)
118+
return reinterpret_cast<const ArrayRef<DynTypedNode> *>(Storage.buffer)
119+
->end();
120+
return reinterpret_cast<const DynTypedNode *>(Storage.buffer) + 1;
121+
}
122+
123+
size_t size() const { return end() - begin(); }
124+
bool empty() const { return begin() == end(); }
125+
126+
const DynTypedNode &operator[](size_t N) const {
127+
assert(N < size() && "Out of bounds!");
128+
return *(begin() + N);
129+
}
130+
};
131+
132+
template <typename NodeT>
133+
inline DynTypedNodeList ParentMapContext::getParents(const NodeT &Node) {
134+
return getParents(ast_type_traits::DynTypedNode::create(Node));
135+
}
136+
137+
template <typename NodeT>
138+
inline DynTypedNodeList ASTContext::getParents(const NodeT &Node) {
139+
return getParentMapContext().getParents(Node);
140+
}
141+
142+
template <>
143+
inline DynTypedNodeList
144+
ASTContext::getParents(const ast_type_traits::DynTypedNode &Node) {
145+
return getParentMapContext().getParents(Node);
146+
}
147+
148+
} // namespace clang
149+
150+
#endif

‎clang/include/clang/ASTMatchers/ASTMatchers.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,7 @@
5252
#include "clang/AST/DeclFriend.h"
5353
#include "clang/AST/DeclObjC.h"
5454
#include "clang/AST/DeclTemplate.h"
55+
#include "clang/AST/ParentMapContext.h"
5556
#include "clang/AST/Expr.h"
5657
#include "clang/AST/ExprCXX.h"
5758
#include "clang/AST/ExprObjC.h"

‎clang/include/clang/Sema/Sema.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,7 @@
1515
#define LLVM_CLANG_SEMA_SEMA_H
1616

1717
#include "clang/AST/ASTConcept.h"
18+
#include "clang/AST/ASTFwd.h"
1819
#include "clang/AST/Attr.h"
1920
#include "clang/AST/Availability.h"
2021
#include "clang/AST/ComparisonCategories.h"

0 commit comments

Comments
 (0)