https://github.com/adamtheturtle updated https://github.com/llvm/llvm-project/pull/235717
>From bceb5c9e772ee91a4ed8baf68ce625b7b9806972 Mon Sep 17 00:00:00 2001 From: Adam Dangoor <[email protected]> Date: Mon, 26 Oct 2026 11:25:19 +0000 Subject: [PATCH] [clang] Avoid repeated traversal of shared C initializer subtrees Fixes https://github.com/llvm/llvm-project/issues/235706 Assisted-by: OpenAI Codex --- .../sizeof-expression-shared-initializers.c | 9 ++++ clang/lib/AST/ParentMapContext.cpp | 6 +++ clang/lib/ASTMatchers/ASTMatchFinder.cpp | 38 ++++++++++++++++ .../Checkers/PaddingChecker.cpp | 7 +++ .../Analysis/padding-shared-initializers.c | 9 ++++ .../unittests/AST/ASTContextParentMapTest.cpp | 41 +++++++++++++++++ .../ASTMatchers/ASTMatchersTraversalTest.cpp | 45 +++++++++++++++++++ 7 files changed, 155 insertions(+) create mode 100644 clang-tools-extra/test/clang-tidy/checkers/bugprone/sizeof-expression-shared-initializers.c create mode 100644 clang/test/Analysis/padding-shared-initializers.c diff --git a/clang-tools-extra/test/clang-tidy/checkers/bugprone/sizeof-expression-shared-initializers.c b/clang-tools-extra/test/clang-tidy/checkers/bugprone/sizeof-expression-shared-initializers.c new file mode 100644 index 00000000000000..5855e0d9a100f2 --- /dev/null +++ b/clang-tools-extra/test/clang-tidy/checkers/bugprone/sizeof-expression-shared-initializers.c @@ -0,0 +1,9 @@ +// RUN: %check_clang_tidy -std=c99 %s bugprone-sizeof-expression %t + +typedef struct V { const struct V *child; } V; +int main(void) { + V value = (V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = 0}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}; + (void)value; + return sizeof(sizeof(int)); +// CHECK-MESSAGES: :[[@LINE-1]]:10: warning: suspicious usage of 'sizeof(sizeof(...))' [bugprone-sizeof-expression] +} diff --git a/clang/lib/AST/ParentMapContext.cpp b/clang/lib/AST/ParentMapContext.cpp index 7607cf27bfe60f..d2859265596974 100644 --- a/clang/lib/AST/ParentMapContext.cpp +++ b/clang/lib/AST/ParentMapContext.cpp @@ -460,6 +460,11 @@ class ParentMapContext::ParentMap::ASTVisitor // Using generic TraverseNode for Stmt would prevent data-recursion. bool dataTraverseStmtPre(Stmt *StmtNode) { addParent(StmtNode, &Map.PointerParents); + // Shared statements can have several parents, but their outgoing edges + // do not depend on the path used to reach them. Record every incoming + // edge before skipping descendants already included in the parent map. + if (!TraversedStmts.insert(StmtNode).second) + return false; ParentStack.push_back(DynTypedNode::create(*StmtNode)); return true; } @@ -469,6 +474,7 @@ class ParentMapContext::ParentMap::ASTVisitor } ParentMap ⤅ + llvm::SmallPtrSet<Stmt *, 32> TraversedStmts; llvm::SmallVector<DynTypedNode, 16> ParentStack; }; diff --git a/clang/lib/ASTMatchers/ASTMatchFinder.cpp b/clang/lib/ASTMatchers/ASTMatchFinder.cpp index 9395b79a7622af..e267fa26f79f1b 100644 --- a/clang/lib/ASTMatchers/ASTMatchFinder.cpp +++ b/clang/lib/ASTMatchers/ASTMatchFinder.cpp @@ -29,6 +29,7 @@ #include <deque> #include <memory> #include <set> +#include <tuple> namespace clang { namespace ast_matchers { @@ -191,8 +192,28 @@ class MatchChildASTVisitor if (!match(*StmtToTraverse)) return false; + // No descendant can match a direct-child query below this depth. + if (CurrentDepth >= MaxDepth) + return true; return VisitorBase::TraverseStmt(StmtToTraverse, Queue); } + // The input bindings and matcher are fixed for this visitor. Cache only + // descendant searches with no matches, preserving successful binding + // multiplicity even when a statement has several incoming AST edges. + bool dataTraverseStmtPre(Stmt *S) { + if (MaxDepth == INT_MAX && NoMatchingDescendants.contains(S)) + return false; + MatchCounts.push_back(MatchCount); + return true; + } + + bool dataTraverseStmtPost(Stmt *S) { + if (MaxDepth == INT_MAX && MatchCounts.back() == MatchCount) + NoMatchingDescendants.insert(S); + MatchCounts.pop_back(); + return true; + } + // We assume that the QualType and the contained type are on the same // hierarchy level. Thus, we try to match either of them. bool TraverseType(QualType TypeNode, bool TraverseQualifier = true) { @@ -379,6 +400,7 @@ class MatchChildASTVisitor if (Matcher->matches(DynTypedNode::create(Node), Finder, &RecursiveBuilder)) { Matches = true; + ++MatchCount; ResultBindings.addMatch(RecursiveBuilder); return false; // Abort as soon as a match is found. } @@ -388,6 +410,7 @@ class MatchChildASTVisitor &RecursiveBuilder)) { // After the first match the matcher succeeds. Matches = true; + ++MatchCount; ResultBindings.addMatch(RecursiveBuilder); } } @@ -414,6 +437,9 @@ class MatchChildASTVisitor const bool IgnoreImplicitChildren; const ASTMatchFinder::BindKind Bind; bool Matches; + size_t MatchCount = 0; + llvm::SmallVector<size_t, 16> MatchCounts; + llvm::SmallPtrSet<const Stmt *, 32> NoMatchingDescendants; }; // Controls the outermost traversal of the AST and allows to match multiple @@ -775,6 +801,8 @@ class MatchASTVisitor : public RecursiveASTVisitor<MatchASTVisitor>, } private: + std::set<std::tuple<const Stmt *, bool, bool, bool>> + TraversedCCompoundLiterals; bool TraversingASTNodeNotSpelledInSource = false; bool TraversingASTNodeNotAsIs = false; bool TraversingASTChildrenNotSpelledInSource = false; @@ -1549,6 +1577,16 @@ bool MatchASTVisitor::TraverseStmt(Stmt *StmtNode, DataRecursionQueue *Queue) { bool ScopedTraversal = TraversingASTNodeNotSpelledInSource || TraversingASTChildrenNotSpelledInSource; + // C designated initializers share compound literals between syntactic + // and semantic forms. Visit each literal once in each traversal context; + // repeating the same subtree adds duplicate callbacks, not new matches. + if (!getASTContext().getLangOpts().CPlusPlus && + isa<CompoundLiteralExpr>(StmtNode) && + !TraversedCCompoundLiterals + .emplace(StmtNode, ScopedTraversal, TraversingASTNodeNotAsIs, + TraversingASTChildrenNotSpelledInSource) + .second) + return true; ASTNodeNotSpelledInSourceScope RAII(this, ScopedTraversal); match(*StmtNode); return RecursiveASTVisitor<MatchASTVisitor>::TraverseStmt(StmtNode, Queue); diff --git a/clang/lib/StaticAnalyzer/Checkers/PaddingChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/PaddingChecker.cpp index 8fd838c8657730..8f940503522960 100644 --- a/clang/lib/StaticAnalyzer/Checkers/PaddingChecker.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/PaddingChecker.cpp @@ -20,6 +20,7 @@ #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" #include "clang/StaticAnalyzer/Core/Checker.h" #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" @@ -44,6 +45,12 @@ class PaddingChecker : public Checker<check::ASTDecl<TranslationUnitDecl>> { // want to visit those, so we make our own RecursiveASTVisitor. struct LocalVisitor : DynamicRecursiveASTVisitor { const PaddingChecker *Checker; + // Padding depends on declarations, not on the path to a shared + // initializer subtree. Still traverse every distinct statement. + llvm::SmallPtrSet<const Stmt *, 32> TraversedStmts; + bool dataTraverseStmtPre(Stmt *S) override { + return TraversedStmts.insert(S).second; + } explicit LocalVisitor(const PaddingChecker *Checker) : Checker(Checker) { ShouldVisitTemplateInstantiations = true; ShouldVisitImplicitCode = true; diff --git a/clang/test/Analysis/padding-shared-initializers.c b/clang/test/Analysis/padding-shared-initializers.c new file mode 100644 index 00000000000000..cc05b60191ad7b --- /dev/null +++ b/clang/test/Analysis/padding-shared-initializers.c @@ -0,0 +1,9 @@ +// RUN: %clang_analyze_cc1 -std=c99 -analyzer-checker=optin.performance.Padding -verify %s +// expected-no-diagnostics + +typedef struct V { const struct V *child; } V; +int main(void) { + V value = (V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = (V[]){(V){.child = 0}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}; + (void)value; + return sizeof(sizeof(int)); +} diff --git a/clang/unittests/AST/ASTContextParentMapTest.cpp b/clang/unittests/AST/ASTContextParentMapTest.cpp index 545eaf36191717..c950b3b72efbff 100644 --- a/clang/unittests/AST/ASTContextParentMapTest.cpp +++ b/clang/unittests/AST/ASTContextParentMapTest.cpp @@ -36,6 +36,47 @@ TEST(GetParents, ReturnsParentForStmt) { ifStmt(hasParent(compoundStmt())))); } +TEST(GetParents, PreservesSharedInitializerEdges) { + auto AST = tooling::buildASTFromCodeWithArgs(R"c( + struct V { const struct V *child; }; + void f(void) { + struct V value = {.child = (struct V[]){{.child = 0}}}; + } + )c", + {"-std=c99"}, "input.c"); + ASSERT_TRUE(AST); + auto &Ctx = AST->getASTContext(); + auto Variables = match(varDecl(hasName("value")).bind("value"), Ctx); + ASSERT_EQ(Variables.size(), 1u); + const auto *Variable = Variables.front().getNodeAs<VarDecl>("value"); + const auto *Init = + dyn_cast<InitListExpr>(Variable->getInit()->IgnoreImplicit()); + ASSERT_TRUE(Init); + ASSERT_TRUE(Init->getSyntacticForm()); + const auto *Designator = + dyn_cast<DesignatedInitExpr>(Init->getSyntacticForm()->getInit(0)); + ASSERT_TRUE(Designator); + const auto *Shared = Init->getInit(0); + ASSERT_EQ(Shared, Designator->getInit()); + + // The syntactic and semantic forms both reference this expression. + EXPECT_THAT(Ctx.getParents(*Shared), + testing::UnorderedElementsAre(DynTypedNode::create(*Init), + DynTypedNode::create(*Designator))); + // Skipping the repeated traversal must not lose its descendants' parents. + const Expr *Descendant = Shared; + while (const auto *Cast = dyn_cast<ImplicitCastExpr>(Descendant)) { + const Expr *Child = Cast->getSubExpr(); + EXPECT_THAT(Ctx.getParents(*Child), + ElementsAre(DynTypedNode::create(*Descendant))); + Descendant = Child; + } + const auto *Literal = dyn_cast<CompoundLiteralExpr>(Descendant); + ASSERT_TRUE(Literal); + EXPECT_THAT(Ctx.getParents(*Literal->getInitializer()), + ElementsAre(DynTypedNode::create(*Literal))); +} + TEST(GetParents, ReturnsParentForTypeLoc) { MatchVerifier<TypeLoc> Verifier; EXPECT_TRUE( diff --git a/clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp b/clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp index a3281f948fdb78..27ed45a0aa96db 100644 --- a/clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp +++ b/clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp @@ -10,6 +10,7 @@ #include "clang/AST/Attr.h" #include "clang/AST/DeclCXX.h" #include "clang/AST/PrettyPrinter.h" +#include "clang/AST/RecursiveASTVisitor.h" #include "clang/ASTMatchers/ASTMatchFinder.h" #include "clang/ASTMatchers/ASTMatchers.h" #include "clang/Tooling/Tooling.h" @@ -5226,6 +5227,50 @@ TEST(ForEachDescendant, BindsMultipleNodes) { std::make_unique<VerifyIdIsBoundTo<FieldDecl>>("f", 4))); } +TEST(ForEachDescendant, PreservesSharedInitializerBindings) { + auto AST = tooling::buildASTFromCodeWithArgs(R"c( + struct V { const struct V *child; }; + void f(void) { + struct V value = { + .child = (struct V[]){{.child = (struct V[]){{.child = 0}}}}}; + } + )c", + {"-std=c99"}, "input.c"); + ASSERT_TRUE(AST); + auto &Ctx = AST->getASTContext(); + auto Functions = match(functionDecl(hasName("f")).bind("f"), Ctx); + ASSERT_EQ(Functions.size(), 1u); + const auto *Function = Functions.front().getNodeAs<FunctionDecl>("f"); + + // A shared subtree still contributes a successful descendant binding for + // each incoming path. Compare with the ordinary visitor's traversal. + struct LiteralVisitor : RecursiveASTVisitor<LiteralVisitor> { + std::vector<const IntegerLiteral *> Literals; + bool shouldVisitImplicitCode() const { return true; } + bool VisitIntegerLiteral(IntegerLiteral *Literal) { + Literals.push_back(Literal); + return true; + } + } Visitor; + Visitor.TraverseDecl(const_cast<FunctionDecl *>(Function)); + ASSERT_GT(Visitor.Literals.size(), 1u); + + auto Results = + match(functionDecl(hasName("f"), + forEachDescendant(integerLiteral().bind("literal"))), + Ctx); + ASSERT_EQ(Results.size(), Visitor.Literals.size()); + for (size_t I = 0; I < Results.size(); ++I) + EXPECT_EQ(Results[I].getNodeAs<IntegerLiteral>("literal"), + Visitor.Literals[I]); + + EXPECT_TRUE(match(functionDecl(hasName("f"), hasDescendant(callExpr())), Ctx) + .empty()); + // The outer traversal reports each compound literal once, while the + // descendant matcher above preserves its successful binding multiplicity. + EXPECT_EQ(match(compoundLiteralExpr(), Ctx).size(), 2u); +} + TEST(ForEachDescendant, BindsRecursiveCombinations) { EXPECT_TRUE(matchAndVerifyResultTrue( "class C { class D { " _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
