[clang-tidy] Avoid expensive AST traversal in RedundantTypenameCheck

[ilovepi]

In Fuchsia, we have several files that take over 2 hours for this check to run, where as it only takes 8 seconds to finish without the RedundantTypenameCheck. We can avoid this exponential behavior by limiting the use of hasAncestor to typeLocs for the types that are actually used in the checking logic.

With this patch, the wall time for the check with --enable-profile goes from 6724 seconds (about 2 hours) to down to a reasonable 0.1753 seconds under c++17, and 347 seconds under C++20.

[llvmbot]

@llvm/pr-subscribers-clang-tools-extra

Author: Paul Kirth (ilovepi)

Changes

In Fuchsia, we have several files that take over 2 hours for this check to run, where as it only takes 8 seconds to finish without the RedundantTypenameCheck. We can avoid this exponential behavior by limiting the use of hasAncestor to typeLocs for the types that are actually used in the checking logic.

With this patch, the wall time for the check with --enable-profile goes from 6724 seconds (about 2 hours) to down to a reasonable 0.1753 seconds.

---

Full diff: https://github.com/llvm/llvm-project/pull/170540.diff

1 Files Affected:

• (modified) clang-tools-extra/clang-tidy/readability/RedundantTypenameCheck.cpp (+7-3)

diff --git a/clang-tools-extra/clang-tidy/readability/RedundantTypenameCheck.cpp b/clang-tools-extra/clang-tidy/readability/RedundantTypenameCheck.cpp
index 5f2519ce9d5c3..f8e576e2a14d7 100644
--- a/clang-tools-extra/clang-tidy/readability/RedundantTypenameCheck.cpp
+++ b/clang-tools-extra/clang-tidy/readability/RedundantTypenameCheck.cpp
@@ -18,9 +18,13 @@ using namespace clang::ast_matchers;
 namespace clang::tidy::readability {
 
 void RedundantTypenameCheck::registerMatchers(MatchFinder *Finder) {
-  Finder->addMatcher(typeLoc(unless(hasAncestor(decl(isInstantiated()))))
-                         .bind("nonDependentTypeLoc"),
-                     this);
+  Finder->addMatcher(
+      typeLoc(loc(TypeMatcher(anyOf(typedefType(), tagType(),
+                                    deducedTemplateSpecializationType(),
+                                    templateSpecializationType()))),
+              unless(hasAncestor(decl(isInstantiated()))))
+          .bind("nonDependentTypeLoc"),
+      this);
 
   if (!getLangOpts().CPlusPlus20)
     return;

[llvmbot]

@llvm/pr-subscribers-clang-tidy

Author: Paul Kirth (ilovepi)

Changes

In Fuchsia, we have several files that take over 2 hours for this check to run, where as it only takes 8 seconds to finish without the RedundantTypenameCheck. We can avoid this exponential behavior by limiting the use of hasAncestor to typeLocs for the types that are actually used in the checking logic.

With this patch, the wall time for the check with --enable-profile goes from 6724 seconds (about 2 hours) to down to a reasonable 0.1753 seconds.

---

Full diff: https://github.com/llvm/llvm-project/pull/170540.diff

1 Files Affected:

• (modified) clang-tools-extra/clang-tidy/readability/RedundantTypenameCheck.cpp (+7-3)

diff --git a/clang-tools-extra/clang-tidy/readability/RedundantTypenameCheck.cpp b/clang-tools-extra/clang-tidy/readability/RedundantTypenameCheck.cpp
index 5f2519ce9d5c3..f8e576e2a14d7 100644
--- a/clang-tools-extra/clang-tidy/readability/RedundantTypenameCheck.cpp
+++ b/clang-tools-extra/clang-tidy/readability/RedundantTypenameCheck.cpp
@@ -18,9 +18,13 @@ using namespace clang::ast_matchers;
 namespace clang::tidy::readability {
 
 void RedundantTypenameCheck::registerMatchers(MatchFinder *Finder) {
-  Finder->addMatcher(typeLoc(unless(hasAncestor(decl(isInstantiated()))))
-                         .bind("nonDependentTypeLoc"),
-                     this);
+  Finder->addMatcher(
+      typeLoc(loc(TypeMatcher(anyOf(typedefType(), tagType(),
+                                    deducedTemplateSpecializationType(),
+                                    templateSpecializationType()))),
+              unless(hasAncestor(decl(isInstantiated()))))
+          .bind("nonDependentTypeLoc"),
+      this);
 
   if (!getLangOpts().CPlusPlus20)
     return;

[5chmidti]

Can't we skip the hasAncestor part (I'd keep the anyOf you added anyways since we are producing less matches that way, which also improves perf)

typeLoc(loc(qualType(unless(dependentNameType())))

?

Then we are not checking a type that is dependent, which eliminates the need for the hasAncestor and also the

      if (NonDependentTypeLoc->getType()->isDependentType())
        return SourceLocation();

later

[zwuis]

It seems that we can remove unless(...). The traverse mode of this checker is TK_IgnoreUnlessSpelledInSource, so decl(isInstantiated()) doesn't matches anything IIUC.

[ilovepi]

Those are great suggestions. Thanks 😃

I’ll try to clean those up and see how our test case works after.

[localspook]

It seems that we can remove unless(...). The traverse mode of this checker is TK_IgnoreUnlessSpelledInSource, so decl(isInstantiated()) doesn't matches anything IIUC.

I originally added the unless to make this test case pass:

llvm-project/clang-tools-extra/test/clang-tidy/checkers/readability/redundant-typename.cpp

Lines 167 to 170 in 5911754

	template <typename T>
	void n(typename T::R *) {}
	template void n<NotDependent>(NotDependent::R *);

Without the unless, we get a false positive; the traversal seems to descend into the instantiation despite the traversal mode being TK_IgnoreUnlessSpelledInSource. Experimenting just now, I tried setting the traversal mode on the matcher explicitly:

  Finder->addMatcher(traverse(TK_IgnoreUnlessSpelledInSource, typeLoc()
                         .bind("nonDependentTypeLoc")),
                     this);

And now it does work! Is there maybe an issue causing the traversal mode to not get propagated?

[localspook]

Ah, bingo. There are a bunch of addMatcher overloads. The ones for DeclarationMatcher and StatementMatcher respect getCheckTraversalKind:

llvm-project/clang/lib/ASTMatchers/ASTMatchFinder.cpp

Lines 1670 to 1680 in 7220268

	void MatchFinder::addMatcher(const DeclarationMatcher &NodeMatch,
	MatchCallback *Action) {
	std::optional<TraversalKind> TK;
	if (Action)
	TK = Action->getCheckTraversalKind();
	if (TK)
	Matchers.DeclOrStmt.emplace_back(traverse(*TK, NodeMatch), Action);
	else
	Matchers.DeclOrStmt.emplace_back(NodeMatch, Action);
	Matchers.AllCallbacks.insert(Action);
	}

And all the rest (including the one we're calling) just... don't?!

llvm-project/clang/lib/ASTMatchers/ASTMatchFinder.cpp

Lines 1712 to 1716 in 7220268

	void MatchFinder::addMatcher(const TypeLocMatcher &NodeMatch,
	MatchCallback *Action) {
	Matchers.TypeLoc.emplace_back(NodeMatch, Action);
	Matchers.AllCallbacks.insert(Action);
	}

[zwuis]

Can we remove TypeMatcher?

-typeLoc(loc(TypeMatcher(anyOf(...))))
+typeLoc(loc(anyOf(...)))