[PATCH] D125675: Optimise findRefs for XRefs and docHighlights
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.
Closed by commit rG2fb6ece2ca83: Optimise findRefs for XRefs and docHighlights
(authored by usaxena95).
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D125675/new/
https://reviews.llvm.org/D125675
Files:
clang-tools-extra/clangd/XRefs.cpp
Index: clang-tools-extra/clangd/XRefs.cpp
===
--- clang-tools-extra/clangd/XRefs.cpp
+++ clang-tools-extra/clangd/XRefs.cpp
@@ -18,6 +18,7 @@
#include "index/Index.h"
#include "index/Merge.h"
#include "index/Relation.h"
+#include "index/SymbolID.h"
#include "index/SymbolLocation.h"
#include "support/Logger.h"
#include "clang/AST/ASTContext.h"
@@ -47,10 +48,12 @@
#include "clang/Index/USRGeneration.h"
#include "clang/Tooling/Syntax/Tokens.h"
#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Error.h"
@@ -397,8 +400,8 @@
}
}
// Special case: void foo() ^override: jump to the overridden method.
-if (NodeKind.isSame(ASTNodeKind::getFromNodeKind()) ||
-NodeKind.isSame(ASTNodeKind::getFromNodeKind())) {
+ if (NodeKind.isSame(ASTNodeKind::getFromNodeKind()) ||
+ NodeKind.isSame(ASTNodeKind::getFromNodeKind())) {
// We may be overridding multiple methods - offer them all.
for (const NamedDecl *ND : CMD->overridden_methods())
AddResultDecl(ND);
@@ -887,8 +890,13 @@
};
ReferenceFinder(const ParsedAST ,
- const llvm::DenseSet , bool PerToken)
- : PerToken(PerToken), AST(AST), TargetIDs(TargetIDs) {}
+ const llvm::ArrayRef Targets, bool PerToken)
+ : PerToken(PerToken), AST(AST) {
+for (const NamedDecl *ND : Targets) {
+ const Decl *CD = ND->getCanonicalDecl();
+ TargetDeclToID[CD] = getSymbolID(CD);
+}
+ }
std::vector take() && {
llvm::sort(References, [](const Reference , const Reference ) {
@@ -913,12 +921,12 @@
llvm::ArrayRef Relations,
SourceLocation Loc,
index::IndexDataConsumer::ASTNodeInfo ASTNode) override {
+auto DeclID = TargetDeclToID.find(D->getCanonicalDecl());
+if (DeclID == TargetDeclToID.end())
+ return true;
const SourceManager = AST.getSourceManager();
if (!isInsideMainFile(Loc, SM))
return true;
-SymbolID ID = getSymbolID(D);
-if (!TargetIDs.contains(ID))
- return true;
const auto = AST.getTokens();
llvm::SmallVector Locs;
@@ -942,7 +950,7 @@
for (SourceLocation L : Locs) {
L = SM.getFileLoc(L);
if (const auto *Tok = TB.spelledTokenAt(L))
-References.push_back({*Tok, Roles, ID});
+References.push_back({*Tok, Roles, DeclID->getSecond()});
}
return true;
}
@@ -951,12 +959,13 @@
bool PerToken; // If true, report 3 references for split ObjC selector names.
std::vector References;
const ParsedAST
- const llvm::DenseSet
+ llvm::DenseMap TargetDeclToID;
};
std::vector
-findRefs(const llvm::DenseSet , ParsedAST , bool PerToken) {
- ReferenceFinder RefFinder(AST, IDs, PerToken);
+findRefs(const llvm::ArrayRef TargetDecls, ParsedAST ,
+ bool PerToken) {
+ ReferenceFinder RefFinder(AST, TargetDecls, PerToken);
index::IndexingOptions IndexOpts;
IndexOpts.SystemSymbolFilter =
index::IndexingOptions::SystemSymbolFilterKind::All;
@@ -1242,16 +1251,12 @@
if (const SelectionTree::Node *N = ST.commonAncestor()) {
DeclRelationSet Relations =
DeclRelation::TemplatePattern | DeclRelation::Alias;
- auto Decls =
- targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver());
- if (!Decls.empty()) {
+ auto TargetDecls=
+ targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver());
+ if (!TargetDecls.empty()) {
// FIXME: we may get multiple DocumentHighlights with the same location
// and different kinds, deduplicate them.
-llvm::DenseSet Targets;
-for (const NamedDecl *ND : Decls)
- if (auto ID = getSymbolID(ND))
-Targets.insert(ID);
-for (const auto : findRefs(Targets, AST, /*PerToken=*/true))
+for (const auto : findRefs(TargetDecls, AST, /*PerToken=*/true))
Result.push_back(toHighlight(Ref, SM));
return true;
}
@@ -1377,12 +1382,12 @@
DeclRelation::TemplatePattern | DeclRelation::Alias;
std::vector Decls =
getDeclAtPosition(AST, *CurLoc, Relations);
-llvm::DenseSet TargetsInMainFile;
+llvm::SmallVector
[PATCH] D125675: Optimise findRefs for XRefs and docHighlights
usaxena95 updated this revision to Diff 429807.
usaxena95 marked 4 inline comments as done.
usaxena95 added a comment.
Addressed comments and added performance measurements.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D125675/new/
https://reviews.llvm.org/D125675
Files:
clang-tools-extra/clangd/XRefs.cpp
Index: clang-tools-extra/clangd/XRefs.cpp
===
--- clang-tools-extra/clangd/XRefs.cpp
+++ clang-tools-extra/clangd/XRefs.cpp
@@ -18,6 +18,7 @@
#include "index/Index.h"
#include "index/Merge.h"
#include "index/Relation.h"
+#include "index/SymbolID.h"
#include "index/SymbolLocation.h"
#include "support/Logger.h"
#include "clang/AST/ASTContext.h"
@@ -47,10 +48,12 @@
#include "clang/Index/USRGeneration.h"
#include "clang/Tooling/Syntax/Tokens.h"
#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Error.h"
@@ -397,8 +400,8 @@
}
}
// Special case: void foo() ^override: jump to the overridden method.
-if (NodeKind.isSame(ASTNodeKind::getFromNodeKind()) ||
-NodeKind.isSame(ASTNodeKind::getFromNodeKind())) {
+ if (NodeKind.isSame(ASTNodeKind::getFromNodeKind()) ||
+ NodeKind.isSame(ASTNodeKind::getFromNodeKind())) {
// We may be overridding multiple methods - offer them all.
for (const NamedDecl *ND : CMD->overridden_methods())
AddResultDecl(ND);
@@ -887,8 +890,13 @@
};
ReferenceFinder(const ParsedAST ,
- const llvm::DenseSet , bool PerToken)
- : PerToken(PerToken), AST(AST), TargetIDs(TargetIDs) {}
+ const llvm::ArrayRef Targets, bool PerToken)
+ : PerToken(PerToken), AST(AST) {
+for (const NamedDecl *ND : Targets) {
+ const Decl *CD = ND->getCanonicalDecl();
+ TargetDeclToID[CD] = getSymbolID(CD);
+}
+ }
std::vector take() && {
llvm::sort(References, [](const Reference , const Reference ) {
@@ -913,12 +921,12 @@
llvm::ArrayRef Relations,
SourceLocation Loc,
index::IndexDataConsumer::ASTNodeInfo ASTNode) override {
+auto DeclID = TargetDeclToID.find(D->getCanonicalDecl());
+if (DeclID == TargetDeclToID.end())
+ return true;
const SourceManager = AST.getSourceManager();
if (!isInsideMainFile(Loc, SM))
return true;
-SymbolID ID = getSymbolID(D);
-if (!TargetIDs.contains(ID))
- return true;
const auto = AST.getTokens();
llvm::SmallVector Locs;
@@ -942,7 +950,7 @@
for (SourceLocation L : Locs) {
L = SM.getFileLoc(L);
if (const auto *Tok = TB.spelledTokenAt(L))
-References.push_back({*Tok, Roles, ID});
+References.push_back({*Tok, Roles, DeclID->getSecond()});
}
return true;
}
@@ -951,12 +959,13 @@
bool PerToken; // If true, report 3 references for split ObjC selector names.
std::vector References;
const ParsedAST
- const llvm::DenseSet
+ llvm::DenseMap TargetDeclToID;
};
std::vector
-findRefs(const llvm::DenseSet , ParsedAST , bool PerToken) {
- ReferenceFinder RefFinder(AST, IDs, PerToken);
+findRefs(const llvm::ArrayRef TargetDecls, ParsedAST ,
+ bool PerToken) {
+ ReferenceFinder RefFinder(AST, TargetDecls, PerToken);
index::IndexingOptions IndexOpts;
IndexOpts.SystemSymbolFilter =
index::IndexingOptions::SystemSymbolFilterKind::All;
@@ -1242,16 +1251,12 @@
if (const SelectionTree::Node *N = ST.commonAncestor()) {
DeclRelationSet Relations =
DeclRelation::TemplatePattern | DeclRelation::Alias;
- auto Decls =
- targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver());
- if (!Decls.empty()) {
+ auto TargetDecls=
+ targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver());
+ if (!TargetDecls.empty()) {
// FIXME: we may get multiple DocumentHighlights with the same location
// and different kinds, deduplicate them.
-llvm::DenseSet Targets;
-for (const NamedDecl *ND : Decls)
- if (auto ID = getSymbolID(ND))
-Targets.insert(ID);
-for (const auto : findRefs(Targets, AST, /*PerToken=*/true))
+for (const auto : findRefs(TargetDecls, AST, /*PerToken=*/true))
Result.push_back(toHighlight(Ref, SM));
return true;
}
@@ -1377,12 +1382,12 @@
DeclRelation::TemplatePattern | DeclRelation::Alias;
std::vector Decls =
getDeclAtPosition(AST, *CurLoc, Relations);
-llvm::DenseSet TargetsInMainFile;
+llvm::SmallVector TargetsInMainFile;
for (const NamedDecl *D : Decls) {
auto
[PATCH] D125675: Optimise findRefs for XRefs and docHighlights
kadircet accepted this revision.
kadircet added a comment.
This revision is now accepted and ready to land.
thanks for noticing this, LGTM!
Comment at: clang-tools-extra/clangd/XRefs.cpp:961
const ParsedAST
- const llvm::DenseSet
+ llvm::DenseMap TargetDeclAndID;
};
s/TargetDeclAndID/TargetDeclToID
Comment at: clang-tools-extra/clangd/XRefs.cpp:965
std::vector
-findRefs(const llvm::DenseSet , ParsedAST , bool PerToken) {
- ReferenceFinder RefFinder(AST, IDs, PerToken);
+findRefs(const llvm::DenseSet , ParsedAST ,
+ bool PerToken) {
i'd actually update the interface here to just take an `ArrayRef` as
targets, as we're currently building those extra dense sets just to iterate
over them. both `allTargetDecls` and `getDeclAtPosition` (which uses
`allTargetDecls` underneath) are guaranteed to not return duplicates. So we can
pass their result directly here. Up to you though.
Comment at: clang-tools-extra/clangd/XRefs.cpp:1919
// If there's a specific type alias, point at that rather than unwrapping.
- if (const auto* TDT = T->getAs())
+ if (const auto *TDT = T->getAs())
return QualType(TDT, 0);
can you revert this change?
Comment at: clang-tools-extra/clangd/XRefs.cpp:951
if (const auto *Tok = TB.spelledTokenAt(L))
-References.push_back({*Tok, Roles, ID});
+References.push_back({*Tok, Roles, getSymbolID(D)});
}
usaxena95 wrote:
> kadircet wrote:
> > we're still calling getsymbolid here lots of times, for probably the same
> > symbol.
> >
> > as discussed, what about building a lookup table on construction from
> > canonicaldecl to symbolid and use that lookup table instead of calling
> > getsymbolid over and over here?
> I don't mind adding a lookup table for this but this is not huge, only
> O(#ref) as compared to previous O(size of TU).
>
>
thanks. previous one was also size of main file, not the whole TU (if you see
indications of the latter in a different application let's take a look at that
separately).
but there are big enough files in which you can have thousands of references to
stringref and what not. so i think this actually matters.
Comment at: clang-tools-extra/clangd/XRefs.cpp:1255
+ targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver())) {
+TargetDecls.insert(D);
+ }
usaxena95 wrote:
> kadircet wrote:
> > i mean directly inserting canonicaldecls here.
> This would make it messy to duplicate this on each end of the call.
> + This has potential of introducing bugs in future findRef calls if we don't
> pass the canonical decls. Or we would have to assert that we only get
> canonical decls.
> I think this is an implementation detail of findRefs and should not be
> visible outside its API for simplicity.
SG, it's an implementation detail of this file already so not a big deal. But
moreover we're building a separate lookup table already now, so obsolete.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D125675/new/
https://reviews.llvm.org/D125675
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D125675: Optimise findRefs for XRefs and docHighlights
usaxena95 updated this revision to Diff 429697.
usaxena95 added a comment.
Format.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D125675/new/
https://reviews.llvm.org/D125675
Files:
clang-tools-extra/clangd/XRefs.cpp
Index: clang-tools-extra/clangd/XRefs.cpp
===
--- clang-tools-extra/clangd/XRefs.cpp
+++ clang-tools-extra/clangd/XRefs.cpp
@@ -18,6 +18,7 @@
#include "index/Index.h"
#include "index/Merge.h"
#include "index/Relation.h"
+#include "index/SymbolID.h"
#include "index/SymbolLocation.h"
#include "support/Logger.h"
#include "clang/AST/ASTContext.h"
@@ -47,6 +48,7 @@
#include "clang/Index/USRGeneration.h"
#include "clang/Tooling/Syntax/Tokens.h"
#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
@@ -397,8 +399,8 @@
}
}
// Special case: void foo() ^override: jump to the overridden method.
-if (NodeKind.isSame(ASTNodeKind::getFromNodeKind()) ||
-NodeKind.isSame(ASTNodeKind::getFromNodeKind())) {
+ if (NodeKind.isSame(ASTNodeKind::getFromNodeKind()) ||
+ NodeKind.isSame(ASTNodeKind::getFromNodeKind())) {
// We may be overridding multiple methods - offer them all.
for (const NamedDecl *ND : CMD->overridden_methods())
AddResultDecl(ND);
@@ -887,8 +889,13 @@
};
ReferenceFinder(const ParsedAST ,
- const llvm::DenseSet , bool PerToken)
- : PerToken(PerToken), AST(AST), TargetIDs(TargetIDs) {}
+ const llvm::DenseSet , bool PerToken)
+ : PerToken(PerToken), AST(AST) {
+for (const Decl *D : Target) {
+ const Decl *CD = D->getCanonicalDecl();
+ TargetDeclAndID[CD] = getSymbolID(CD);
+}
+ }
std::vector take() && {
llvm::sort(References, [](const Reference , const Reference ) {
@@ -913,12 +920,12 @@
llvm::ArrayRef Relations,
SourceLocation Loc,
index::IndexDataConsumer::ASTNodeInfo ASTNode) override {
+auto DeclID = TargetDeclAndID.find(D->getCanonicalDecl());
+if (DeclID == TargetDeclAndID.end())
+ return true;
const SourceManager = AST.getSourceManager();
if (!isInsideMainFile(Loc, SM))
return true;
-SymbolID ID = getSymbolID(D);
-if (!TargetIDs.contains(ID))
- return true;
const auto = AST.getTokens();
llvm::SmallVector Locs;
@@ -942,7 +949,7 @@
for (SourceLocation L : Locs) {
L = SM.getFileLoc(L);
if (const auto *Tok = TB.spelledTokenAt(L))
-References.push_back({*Tok, Roles, ID});
+References.push_back({*Tok, Roles, DeclID->getSecond()});
}
return true;
}
@@ -951,12 +958,13 @@
bool PerToken; // If true, report 3 references for split ObjC selector names.
std::vector References;
const ParsedAST
- const llvm::DenseSet
+ llvm::DenseMap TargetDeclAndID;
};
std::vector
-findRefs(const llvm::DenseSet , ParsedAST , bool PerToken) {
- ReferenceFinder RefFinder(AST, IDs, PerToken);
+findRefs(const llvm::DenseSet , ParsedAST ,
+ bool PerToken) {
+ ReferenceFinder RefFinder(AST, TargetDecls, PerToken);
index::IndexingOptions IndexOpts;
IndexOpts.SystemSymbolFilter =
index::IndexingOptions::SystemSymbolFilterKind::All;
@@ -1242,16 +1250,15 @@
if (const SelectionTree::Node *N = ST.commonAncestor()) {
DeclRelationSet Relations =
DeclRelation::TemplatePattern | DeclRelation::Alias;
- auto Decls =
- targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver());
- if (!Decls.empty()) {
+ llvm::DenseSet TargetDecls;
+ for (const NamedDecl *D :
+ targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver())) {
+TargetDecls.insert(D);
+ }
+ if (!TargetDecls.empty()) {
// FIXME: we may get multiple DocumentHighlights with the same location
// and different kinds, deduplicate them.
-llvm::DenseSet Targets;
-for (const NamedDecl *ND : Decls)
- if (auto ID = getSymbolID(ND))
-Targets.insert(ID);
-for (const auto : findRefs(Targets, AST, /*PerToken=*/true))
+for (const auto : findRefs(TargetDecls, AST, /*PerToken=*/true))
Result.push_back(toHighlight(Ref, SM));
return true;
}
@@ -1377,12 +1384,12 @@
DeclRelation::TemplatePattern | DeclRelation::Alias;
std::vector Decls =
getDeclAtPosition(AST, *CurLoc, Relations);
-llvm::DenseSet TargetsInMainFile;
+llvm::DenseSet TargetsInMainFile;
for (const NamedDecl *D : Decls) {
auto ID = getSymbolID(D);
if (!ID)
continue;
- TargetsInMainFile.insert(ID);
+ TargetsInMainFile.insert(D);
// Not all symbols can be referenced from outside (e.g.
[PATCH] D125675: Optimise findRefs for XRefs and docHighlights
usaxena95 added inline comments.
Comment at: clang-tools-extra/clangd/XRefs.cpp:951
if (const auto *Tok = TB.spelledTokenAt(L))
-References.push_back({*Tok, Roles, ID});
+References.push_back({*Tok, Roles, getSymbolID(D)});
}
kadircet wrote:
> we're still calling getsymbolid here lots of times, for probably the same
> symbol.
>
> as discussed, what about building a lookup table on construction from
> canonicaldecl to symbolid and use that lookup table instead of calling
> getsymbolid over and over here?
I don't mind adding a lookup table for this but this is not huge, only O(#ref)
as compared to previous O(size of TU).
Comment at: clang-tools-extra/clangd/XRefs.cpp:1255
+ targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver())) {
+TargetDecls.insert(D);
+ }
kadircet wrote:
> i mean directly inserting canonicaldecls here.
This would make it messy to duplicate this on each end of the call.
+ This has potential of introducing bugs in future findRef calls if we don't
pass the canonical decls. Or we would have to assert that we only get canonical
decls.
I think this is an implementation detail of findRefs and should not be visible
outside its API for simplicity.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D125675/new/
https://reviews.llvm.org/D125675
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D125675: Optimise findRefs for XRefs and docHighlights
usaxena95 updated this revision to Diff 429696.
usaxena95 marked 4 inline comments as done.
usaxena95 added a comment.
Address comments.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D125675/new/
https://reviews.llvm.org/D125675
Files:
clang-tools-extra/clangd/XRefs.cpp
Index: clang-tools-extra/clangd/XRefs.cpp
===
--- clang-tools-extra/clangd/XRefs.cpp
+++ clang-tools-extra/clangd/XRefs.cpp
@@ -18,6 +18,7 @@
#include "index/Index.h"
#include "index/Merge.h"
#include "index/Relation.h"
+#include "index/SymbolID.h"
#include "index/SymbolLocation.h"
#include "support/Logger.h"
#include "clang/AST/ASTContext.h"
@@ -47,6 +48,7 @@
#include "clang/Index/USRGeneration.h"
#include "clang/Tooling/Syntax/Tokens.h"
#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
@@ -397,8 +399,8 @@
}
}
// Special case: void foo() ^override: jump to the overridden method.
-if (NodeKind.isSame(ASTNodeKind::getFromNodeKind()) ||
-NodeKind.isSame(ASTNodeKind::getFromNodeKind())) {
+ if (NodeKind.isSame(ASTNodeKind::getFromNodeKind()) ||
+ NodeKind.isSame(ASTNodeKind::getFromNodeKind())) {
// We may be overridding multiple methods - offer them all.
for (const NamedDecl *ND : CMD->overridden_methods())
AddResultDecl(ND);
@@ -887,8 +889,13 @@
};
ReferenceFinder(const ParsedAST ,
- const llvm::DenseSet , bool PerToken)
- : PerToken(PerToken), AST(AST), TargetIDs(TargetIDs) {}
+ const llvm::DenseSet , bool PerToken)
+ : PerToken(PerToken), AST(AST) {
+for (const Decl *D : Target) {
+ const Decl *CD = D->getCanonicalDecl();
+ TargetDeclAndID[CD] = getSymbolID(CD);
+}
+ }
std::vector take() && {
llvm::sort(References, [](const Reference , const Reference ) {
@@ -913,12 +920,12 @@
llvm::ArrayRef Relations,
SourceLocation Loc,
index::IndexDataConsumer::ASTNodeInfo ASTNode) override {
+auto DeclID = TargetDeclAndID.find(D->getCanonicalDecl());
+if (DeclID == TargetDeclAndID.end())
+ return true;
const SourceManager = AST.getSourceManager();
if (!isInsideMainFile(Loc, SM))
return true;
-SymbolID ID = getSymbolID(D);
-if (!TargetIDs.contains(ID))
- return true;
const auto = AST.getTokens();
llvm::SmallVector Locs;
@@ -942,7 +949,7 @@
for (SourceLocation L : Locs) {
L = SM.getFileLoc(L);
if (const auto *Tok = TB.spelledTokenAt(L))
-References.push_back({*Tok, Roles, ID});
+References.push_back({*Tok, Roles, DeclID->getSecond()});
}
return true;
}
@@ -951,12 +958,13 @@
bool PerToken; // If true, report 3 references for split ObjC selector names.
std::vector References;
const ParsedAST
- const llvm::DenseSet
+ llvm::DenseMap TargetDeclAndID;
};
std::vector
-findRefs(const llvm::DenseSet , ParsedAST , bool PerToken) {
- ReferenceFinder RefFinder(AST, IDs, PerToken);
+findRefs(const llvm::DenseSet , ParsedAST ,
+ bool PerToken) {
+ ReferenceFinder RefFinder(AST, TargetDecls, PerToken);
index::IndexingOptions IndexOpts;
IndexOpts.SystemSymbolFilter =
index::IndexingOptions::SystemSymbolFilterKind::All;
@@ -1242,16 +1250,15 @@
if (const SelectionTree::Node *N = ST.commonAncestor()) {
DeclRelationSet Relations =
DeclRelation::TemplatePattern | DeclRelation::Alias;
- auto Decls =
- targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver());
- if (!Decls.empty()) {
+ llvm::DenseSet TargetDecls;
+ for (const NamedDecl *D :
+ targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver())) {
+TargetDecls.insert(D);
+ }
+ if (!TargetDecls.empty()) {
// FIXME: we may get multiple DocumentHighlights with the same location
// and different kinds, deduplicate them.
-llvm::DenseSet Targets;
-for (const NamedDecl *ND : Decls)
- if (auto ID = getSymbolID(ND))
-Targets.insert(ID);
-for (const auto : findRefs(Targets, AST, /*PerToken=*/true))
+for (const auto : findRefs(TargetDecls, AST, /*PerToken=*/true))
Result.push_back(toHighlight(Ref, SM));
return true;
}
@@ -1377,12 +1384,12 @@
DeclRelation::TemplatePattern | DeclRelation::Alias;
std::vector Decls =
getDeclAtPosition(AST, *CurLoc, Relations);
-llvm::DenseSet TargetsInMainFile;
+llvm::DenseSet TargetInMainFile;
for (const NamedDecl *D : Decls) {
auto ID = getSymbolID(D);
if (!ID)
continue;
- TargetsInMainFile.insert(ID);
+ TargetInMainFile.insert(D);
// Not all
[PATCH] D125675: Optimise findRefs for XRefs and docHighlights
kadircet added a reviewer: kadircet.
kadircet added a comment.
66% win sounds great, it would be nice to have some detailed numbers (but this
is clearly a huge win, so no need to reperform the experiments if numbers are
gone)
Comment at: clang-tools-extra/clangd/XRefs.cpp:895
+ : PerToken(PerToken), AST(AST) {
+for (const Decl *D : TD) {
+ TargetDecls.insert(D->getCanonicalDecl());
nit: no need for braces
you can directly build the set with canonicaldecls and consume it here
Comment at: clang-tools-extra/clangd/XRefs.cpp:951
if (const auto *Tok = TB.spelledTokenAt(L))
-References.push_back({*Tok, Roles, ID});
+References.push_back({*Tok, Roles, getSymbolID(D)});
}
we're still calling getsymbolid here lots of times, for probably the same
symbol.
as discussed, what about building a lookup table on construction from
canonicaldecl to symbolid and use that lookup table instead of calling
getsymbolid over and over here?
Comment at: clang-tools-extra/clangd/XRefs.cpp:1255
+ targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver())) {
+TargetDecls.insert(D);
+ }
i mean directly inserting canonicaldecls here.
Comment at: clang-tools-extra/clangd/XRefs.cpp:1260
// and different kinds, deduplicate them.
llvm::DenseSet Targets;
+for (const Decl *D : TargetDecls)
no need for this and the following loop anymore.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D125675/new/
https://reviews.llvm.org/D125675
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D125675: Optimise findRefs for XRefs and docHighlights
usaxena95 created this revision.
Herald added subscribers: kadircet, arphaman.
Herald added a project: All.
usaxena95 requested review of this revision.
Herald added a project: clang-tools-extra.
Herald added a subscriber: cfe-commits.
Reduces time spent in findRef by 66%.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D125675
Files:
clang-tools-extra/clangd/XRefs.cpp
Index: clang-tools-extra/clangd/XRefs.cpp
===
--- clang-tools-extra/clangd/XRefs.cpp
+++ clang-tools-extra/clangd/XRefs.cpp
@@ -18,6 +18,7 @@
#include "index/Index.h"
#include "index/Merge.h"
#include "index/Relation.h"
+#include "index/SymbolID.h"
#include "index/SymbolLocation.h"
#include "support/Logger.h"
#include "clang/AST/ASTContext.h"
@@ -47,6 +48,7 @@
#include "clang/Index/USRGeneration.h"
#include "clang/Tooling/Syntax/Tokens.h"
#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
@@ -54,6 +56,7 @@
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Error.h"
+#include "llvm/ADT/DenseSet.h"
#include "llvm/Support/Path.h"
#include "llvm/Support/raw_ostream.h"
@@ -887,8 +890,12 @@
};
ReferenceFinder(const ParsedAST ,
- const llvm::DenseSet , bool PerToken)
- : PerToken(PerToken), AST(AST), TargetIDs(TargetIDs) {}
+ const llvm::DenseSet , bool PerToken)
+ : PerToken(PerToken), AST(AST) {
+for (const Decl *D : TD) {
+ TargetDecls.insert(D->getCanonicalDecl());
+}
+ }
std::vector take() && {
llvm::sort(References, [](const Reference , const Reference ) {
@@ -913,12 +920,11 @@
llvm::ArrayRef Relations,
SourceLocation Loc,
index::IndexDataConsumer::ASTNodeInfo ASTNode) override {
+if (!TargetDecls.contains(D->getCanonicalDecl()))
+ return true;
const SourceManager = AST.getSourceManager();
if (!isInsideMainFile(Loc, SM))
return true;
-SymbolID ID = getSymbolID(D);
-if (!TargetIDs.contains(ID))
- return true;
const auto = AST.getTokens();
llvm::SmallVector Locs;
@@ -942,7 +948,7 @@
for (SourceLocation L : Locs) {
L = SM.getFileLoc(L);
if (const auto *Tok = TB.spelledTokenAt(L))
-References.push_back({*Tok, Roles, ID});
+References.push_back({*Tok, Roles, getSymbolID(D)});
}
return true;
}
@@ -951,12 +957,13 @@
bool PerToken; // If true, report 3 references for split ObjC selector names.
std::vector References;
const ParsedAST
- const llvm::DenseSet
+ llvm::DenseSet TargetDecls;
};
std::vector
-findRefs(const llvm::DenseSet , ParsedAST , bool PerToken) {
- ReferenceFinder RefFinder(AST, IDs, PerToken);
+findRefs(const llvm::DenseSet , ParsedAST ,
+ bool PerToken) {
+ ReferenceFinder RefFinder(AST, TargetDecls, PerToken);
index::IndexingOptions IndexOpts;
IndexOpts.SystemSymbolFilter =
index::IndexingOptions::SystemSymbolFilterKind::All;
@@ -1242,16 +1249,19 @@
if (const SelectionTree::Node *N = ST.commonAncestor()) {
DeclRelationSet Relations =
DeclRelation::TemplatePattern | DeclRelation::Alias;
- auto Decls =
- targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver());
- if (!Decls.empty()) {
+ llvm::DenseSet TargetDecls;
+ for (const NamedDecl *D :
+ targetDecl(N->ASTNode, Relations, AST.getHeuristicResolver())) {
+TargetDecls.insert(D);
+ }
+ if (!TargetDecls.empty()) {
// FIXME: we may get multiple DocumentHighlights with the same location
// and different kinds, deduplicate them.
llvm::DenseSet Targets;
-for (const NamedDecl *ND : Decls)
- if (auto ID = getSymbolID(ND))
+for (const Decl *D : TargetDecls)
+ if (auto ID = getSymbolID(D))
Targets.insert(ID);
-for (const auto : findRefs(Targets, AST, /*PerToken=*/true))
+for (const auto : findRefs(TargetDecls, AST, /*PerToken=*/true))
Result.push_back(toHighlight(Ref, SM));
return true;
}
@@ -1377,12 +1387,12 @@
DeclRelation::TemplatePattern | DeclRelation::Alias;
std::vector Decls =
getDeclAtPosition(AST, *CurLoc, Relations);
-llvm::DenseSet TargetsInMainFile;
+llvm::DenseSet TargetDeclsInMainFile;
for (const NamedDecl *D : Decls) {
auto ID = getSymbolID(D);
if (!ID)
continue;
- TargetsInMainFile.insert(ID);
+ TargetDeclsInMainFile.insert(D);
// Not all symbols can be referenced from outside (e.g. function-locals).
// TODO: we could skip TU-scoped symbols here (e.g. static functions) if
// we know this file isn't a header. The details might be tricky.
@@ -1408,7 +1418,8 @@
