njames93 updated this revision to Diff 400266.
njames93 added a comment.
Add support for array access `Arr[I * JExtent + J]`
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D116875/new/
https://reviews.llvm.org/D116875
Files:
clang-tools-extra/clang-tidy/performance/CMakeLists.txt
clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.cpp
clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.h
clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp
clang-tools-extra/docs/ReleaseNotes.rst
clang-tools-extra/docs/clang-tidy/checks/list.rst
clang-tools-extra/docs/clang-tidy/checks/performance-inefficient-array-traversal.rst
clang-tools-extra/test/clang-tidy/checkers/performance-inefficient-array-traversal.cpp
Index: clang-tools-extra/test/clang-tidy/checkers/performance-inefficient-array-traversal.cpp
===================================================================
--- /dev/null
+++ clang-tools-extra/test/clang-tidy/checkers/performance-inefficient-array-traversal.cpp
@@ -0,0 +1,107 @@
+// RUN: %check_clang_tidy %s performance-inefficient-array-traversal %t
+
+constexpr unsigned Rows = 10U;
+constexpr unsigned Cols = 16U;
+
+int Arr[Rows][Cols];
+int *PtrArr[Cols];
+int **Ptr;
+int FlatArray[Rows * Cols];
+
+void foo();
+
+void warned() {
+ for (unsigned I = 0; I < Cols; ++I) {
+ for (unsigned J = 0; J < Rows; ++J) {
+ Arr[J][I]++;
+ // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: Nonsequential array traversal can harm performance
+ // CHECK-MESSAGES: :[[@LINE-3]]:5: note: Row index 'J' incremented in this loop
+ // CHECK-MESSAGES: :[[@LINE-5]]:3: note: Column index 'I' incremented in this loop
+ }
+ }
+ for (unsigned I = 0; I < Cols; ++I)
+ for (unsigned J = 0; J < Rows; ++J)
+ Arr[J][I]++;
+ // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: Nonsequential array traversal can harm performance
+
+ // Ensure it works on array access that use pointers
+ for (unsigned I = 0; I < Cols; ++I)
+ for (unsigned J = 0; J < Rows; ++J)
+ PtrArr[J][I]++;
+ // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: Nonsequential array traversal can harm performance
+
+ for (unsigned I = 0; I < Cols; ++I)
+ for (unsigned J = 0; J < Rows; ++J)
+ Ptr[J][I]++;
+ // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: Nonsequential array traversal can harm performance
+
+ // Detect += 1 as the loop incriment
+ for (unsigned I = 0; I < Cols; I += 1)
+ for (unsigned J = 0; J < Rows; J += 1)
+ Arr[J][I]++;
+ // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: Nonsequential array traversal can harm performance
+
+ // Still warn on this as calls inside the inner loop shouldn't complicate a fix.
+ for (unsigned I = 0; I < Cols; ++I) {
+ for (unsigned J = 0; J < Rows; ++J) {
+ foo();
+ Arr[J][I]++;
+ // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: Nonsequential array traversal can harm performance
+ foo();
+ }
+ }
+ for (unsigned I = 0; I < Cols; ++I) {
+ for (unsigned J = 0; J < Rows; ++J) {
+ FlatArray[J * Cols + I]++;
+ // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: Nonsequential array traversal can harm performance
+ // CHECK-MESSAGES: :[[@LINE-3]]:5: note: Row index 'J' incremented in this loop
+ // CHECK-MESSAGES: :[[@LINE-5]]:3: note: Column index 'I' incremented in this loop
+ }
+ }
+}
+
+void ignored() {
+ // Correct traversal.
+ for (unsigned I = 0; I < Rows; ++I) {
+ for (unsigned J = 0; J < Cols; ++J) {
+ Arr[I][J]++;
+ }
+ }
+ for (unsigned I = 0; I < Rows; ++I) {
+ for (unsigned J = 0; J < Cols; ++J) {
+ PtrArr[I][J]++;
+ }
+ }
+ for (unsigned I = 0; I < Rows; ++I) {
+ for (unsigned J = 0; J < Cols; ++J) {
+ FlatArray[I * Cols + J]++;
+ }
+ }
+ // Don'w warn on these cases as extra code inside the outer loop could complicate a fix.
+ for (unsigned I = 0; I < Cols; ++I) {
+ foo();
+ for (unsigned J = 0; J < Rows; ++J) {
+ Arr[J][I]++;
+ }
+ }
+ for (unsigned I = 0; I < Cols; ++I) {
+ for (unsigned J = 0; J < Rows; ++J) {
+ Arr[J][I]++;
+ }
+ foo();
+ }
+
+ // Nested loop increments incorrect variable, don't warn on the traversal.
+ for (unsigned I = 0; I < Cols; ++I)
+ for (unsigned J = 0; J < Rows; ++I)
+ Arr[J][I]++;
+
+ // These 2 loops are questionable and definitely a memory safety bug,
+ // but this is not the point of this check.
+ for (unsigned I = 0; I < Cols; ++I)
+ for (unsigned J = 0; J < Rows; ++I)
+ FlatArray[I * Cols + J]++;
+ for (unsigned I = 0; I < Rows; ++I)
+ for (unsigned J = 0; J < Cols; ++I)
+ FlatArray[J * Rows + I]++;
+}
Index: clang-tools-extra/docs/clang-tidy/checks/performance-inefficient-array-traversal.rst
===================================================================
--- /dev/null
+++ clang-tools-extra/docs/clang-tidy/checks/performance-inefficient-array-traversal.rst
@@ -0,0 +1,24 @@
+.. title:: clang-tidy - performance-inefficient-array-traversal
+
+performance-inefficient-array-traversal
+=======================================
+
+Detects nested ``for`` loops used to traverse a 2D array where the row index
+is iterated on the inner loop.
+
+.. code-block:: c++
+
+ for (int X = 0; X < Columns; ++X)
+ for (int Y = 0; Y < Rows; ++Y)
+ Array[Y][X]++;
+
+This array access pattern results in nonsequential data access which is cache
+unfriendly and can prevent auto vectorization optimizations.
+
+A much faster version of the above loop would be
+
+.. code-block:: c++
+
+ for (int Y = 0; Y < Rows; ++Y)
+ for (int X = 0; X < Columns; ++X)
+ Array[Y][X]++;
Index: clang-tools-extra/docs/clang-tidy/checks/list.rst
===================================================================
--- clang-tools-extra/docs/clang-tidy/checks/list.rst
+++ clang-tools-extra/docs/clang-tidy/checks/list.rst
@@ -273,6 +273,7 @@
`performance-for-range-copy <performance-for-range-copy.html>`_, "Yes"
`performance-implicit-conversion-in-loop <performance-implicit-conversion-in-loop.html>`_,
`performance-inefficient-algorithm <performance-inefficient-algorithm.html>`_, "Yes"
+ `performance-inefficient-array-traversal <performance-inefficient-array-traversal.html>`_,
`performance-inefficient-string-concatenation <performance-inefficient-string-concatenation.html>`_,
`performance-inefficient-vector-operation <performance-inefficient-vector-operation.html>`_, "Yes"
`performance-move-const-arg <performance-move-const-arg.html>`_, "Yes"
Index: clang-tools-extra/docs/ReleaseNotes.rst
===================================================================
--- clang-tools-extra/docs/ReleaseNotes.rst
+++ clang-tools-extra/docs/ReleaseNotes.rst
@@ -111,6 +111,12 @@
Reports identifier with unicode right-to-left characters.
+- New :doc:`performance-inefficient-array-traversal
+ <clang-tidy/checks/performance-inefficient-array-traversal>` check.
+
+ Detects nested ``for`` loops used to traverse a 2D array where the row index
+ is iterated on the inner loop.
+
- New :doc:`readability-container-data-pointer
<clang-tidy/checks/readability-container-data-pointer>` check.
Index: clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp
===================================================================
--- clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp
+++ clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp
@@ -13,6 +13,7 @@
#include "ForRangeCopyCheck.h"
#include "ImplicitConversionInLoopCheck.h"
#include "InefficientAlgorithmCheck.h"
+#include "InefficientArrayTraversalCheck.h"
#include "InefficientStringConcatenationCheck.h"
#include "InefficientVectorOperationCheck.h"
#include "MoveConstArgCheck.h"
@@ -40,6 +41,8 @@
"performance-implicit-conversion-in-loop");
CheckFactories.registerCheck<InefficientAlgorithmCheck>(
"performance-inefficient-algorithm");
+ CheckFactories.registerCheck<InefficientArrayTraversalCheck>(
+ "performance-inefficient-array-traversal");
CheckFactories.registerCheck<InefficientStringConcatenationCheck>(
"performance-inefficient-string-concatenation");
CheckFactories.registerCheck<InefficientVectorOperationCheck>(
Index: clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.h
===================================================================
--- /dev/null
+++ clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.h
@@ -0,0 +1,38 @@
+//===--- InefficientArrayTraversalCheck.h - clang-tidy ----------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENTARRAYTRAVERSALCHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENTARRAYTRAVERSALCHECK_H
+
+#include "../ClangTidyCheck.h"
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+/// Detects nested for loops used to traverse a 2D array where the row index is
+/// iterated on the inner loop.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/performance-inefficient-array-traversal.html
+class InefficientArrayTraversalCheck : public ClangTidyCheck {
+public:
+ InefficientArrayTraversalCheck(StringRef Name, ClangTidyContext *Context)
+ : ClangTidyCheck(Name, Context) {}
+ void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+ void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+ llvm::Optional<TraversalKind> getCheckTraversalKind() const override {
+ return TK_IgnoreUnlessSpelledInSource;
+ }
+};
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENTARRAYTRAVERSALCHECK_H
Index: clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.cpp
===================================================================
--- /dev/null
+++ clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.cpp
@@ -0,0 +1,156 @@
+//===--- InefficientArrayTraversalCheck.cpp - clang-tidy ------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "InefficientArrayTraversalCheck.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+namespace {
+AST_MATCHER_P(Stmt, hasSingleStmt, ast_matchers::internal::Matcher<Stmt>,
+ InnerMatch) {
+ clang::ast_matchers::internal::BoundNodesTreeBuilder Copy(*Builder);
+ if (InnerMatch.matches(Node, Finder, &Copy)) {
+ *Builder = Copy;
+ return true;
+ }
+ if (const auto *Res = dyn_cast<CompoundStmt>(&Node)) {
+ return Res->size() == 1 &&
+ InnerMatch.matches(*Res->body_front(), Finder, Builder);
+ }
+ return false;
+}
+ast_matchers::internal::Matcher<Stmt>
+stmtOrCompound(ast_matchers::internal::Matcher<Stmt> Inner) {
+ return anyOf(Inner, compoundStmt(hasAnySubstatement(Inner)));
+}
+AST_MATCHER_P2(Expr, isEquivalentToEither, StringRef, LHSBound, StringRef,
+ RHSBound) {
+ llvm::FoldingSetNodeID ExprID, MatchedID;
+ Node.Profile(ExprID, Finder->getASTContext(), true);
+ return Builder->removeBindings(
+ [this, &ExprID, &MatchedID,
+ Finder](const ast_matchers::internal::BoundNodesMap &Nodes) {
+ for (const auto &Item : {&LHSBound, &RHSBound}) {
+ const auto *MatchedExpr = Nodes.getNodeAs<Expr>(*Item);
+ MatchedID.clear();
+ if (MatchedExpr) {
+ MatchedExpr->Profile(MatchedID, Finder->getASTContext(), true);
+ if (MatchedID == ExprID)
+ return false;
+ }
+ }
+ return true;
+ });
+}
+} // namespace
+
+static const char InnerVar[] = "InnerVar";
+static const char OuterVar[] = "OuterVar";
+static const char OuterExtent[] = "OuterExtent";
+static const char OuterInit[] = "OuterInit";
+static const char InnerLoop[] = "InnerLoop";
+static const char OuterLoop[] = "OuterLoop";
+static const char ArrayAccess[] = "ArrayAccess";
+static const char StridedArrayAccess[] = "Strided";
+
+void InefficientArrayTraversalCheck::registerMatchers(MatchFinder *Finder) {
+ auto NestedLoopMatcher = [](auto InnerLoopBody) {
+ auto ForLoopBase = [](auto BodyMatcher, bool Inner) {
+ StringRef Var = Inner ? InnerVar : OuterVar;
+ auto ToDecl = declRefExpr(hasDeclaration(equalsBoundNode(Var.str())));
+ return forStmt(hasLoopInit(declStmt(hasSingleDecl(
+ varDecl(hasType(isInteger()),
+ Inner ? anything()
+ : hasInitializer(ignoringParenImpCasts(
+ expr().bind(OuterInit))))
+ .bind(Var)))),
+ hasCondition(binaryOperator(
+ Inner ? binaryOperator(hasEitherOperand(ToDecl))
+ : binaryOperator(hasOperands(
+ ToDecl, ignoringParenImpCasts(
+ expr().bind(OuterExtent)))),
+ hasAnyOperatorName("<", ">", "!=", ">=", "<="))),
+ // TODO: Add support for x = x [+-] 1
+ hasIncrement(anyOf(
+ unaryOperator(hasUnaryOperand(ToDecl),
+ hasAnyOperatorName("++", "--")),
+ binaryOperator(hasAnyOperatorName("+=", "-="),
+ hasLHS(ToDecl),
+ hasRHS(integerLiteral(equals(1)))))),
+ hasBody(BodyMatcher))
+ .bind(Inner ? InnerLoop : OuterLoop);
+ };
+ return ForLoopBase(
+ hasSingleStmt(ForLoopBase(stmtOrCompound(InnerLoopBody), true)), false);
+ };
+ auto ArrayExprMatcher = expr(hasDescendant(
+ arraySubscriptExpr(
+ hasIndex(declRefExpr(hasDeclaration(equalsBoundNode(OuterVar)))),
+ hasBase(arraySubscriptExpr(hasIndex(
+ declRefExpr(hasDeclaration(equalsBoundNode(InnerVar)))))))
+ .bind(ArrayAccess)));
+ auto StridedAccess = expr(hasDescendant(
+ arraySubscriptExpr(
+ hasIndex(binaryOperator(
+ hasOperatorName("+"),
+ hasOperands(
+ declRefExpr(hasDeclaration(equalsBoundNode(OuterVar))),
+ binaryOperator(hasOperatorName("*"),
+ hasOperands(declRefExpr(hasDeclaration(
+ equalsBoundNode(InnerVar))),
+ isEquivalentToEither(
+ OuterInit, OuterExtent)))))))
+ .bind(StridedArrayAccess)));
+ Finder->addMatcher(NestedLoopMatcher(ArrayExprMatcher), this);
+ Finder->addMatcher(NestedLoopMatcher(StridedAccess), this);
+ // TODO: Add a matcher that works for containers
+ // VectorOfVectors[InnerVar][OuterVar]
+}
+
+void InefficientArrayTraversalCheck::check(
+ const MatchFinder::MatchResult &Result) {
+ auto DisplayLoops = [this, &Result] {
+ const auto *InnerLoopStmt = Result.Nodes.getNodeAs<ForStmt>(InnerLoop);
+ diag(InnerLoopStmt->getBeginLoc(), "Row index %0 incremented in this loop",
+ DiagnosticIDs::Note)
+ << Result.Nodes.getNodeAs<VarDecl>(InnerVar)
+ << SourceRange(InnerLoopStmt->getBeginLoc(),
+ InnerLoopStmt->getRParenLoc());
+ const auto *OuterLoopStmt = Result.Nodes.getNodeAs<ForStmt>(OuterLoop);
+ diag(OuterLoopStmt->getBeginLoc(),
+ "Column index %0 incremented in this loop", DiagnosticIDs::Note)
+ << Result.Nodes.getNodeAs<VarDecl>(OuterVar)
+ << SourceRange(OuterLoopStmt->getBeginLoc(),
+ OuterLoopStmt->getRParenLoc());
+ };
+ if (const auto *Array =
+ Result.Nodes.getNodeAs<ArraySubscriptExpr>(ArrayAccess)) {
+ diag(Array->getBeginLoc(),
+ "Nonsequential array traversal can harm performance");
+ DisplayLoops();
+ return;
+ }
+ if (const auto *Array =
+ Result.Nodes.getNodeAs<ArraySubscriptExpr>(StridedArrayAccess)) {
+ diag(Array->getBeginLoc(),
+ "Nonsequential array traversal can harm performance");
+ DisplayLoops();
+ return;
+ }
+ llvm_unreachable("Unhandled Match");
+}
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang
Index: clang-tools-extra/clang-tidy/performance/CMakeLists.txt
===================================================================
--- clang-tools-extra/clang-tidy/performance/CMakeLists.txt
+++ clang-tools-extra/clang-tidy/performance/CMakeLists.txt
@@ -8,6 +8,7 @@
ForRangeCopyCheck.cpp
ImplicitConversionInLoopCheck.cpp
InefficientAlgorithmCheck.cpp
+ InefficientArrayTraversalCheck.cpp
InefficientStringConcatenationCheck.cpp
InefficientVectorOperationCheck.cpp
MoveConstArgCheck.cpp
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
