diff --git a/clang-tools-extra/clang-tidy/performance/CMakeLists.txt b/clang-tools-extra/clang-tidy/performance/CMakeLists.txt --- a/clang-tools-extra/clang-tidy/performance/CMakeLists.txt +++ b/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 diff --git a/clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.h b/clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.h new file mode 100644 --- /dev/null +++ b/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 getCheckTraversalKind() const override { + return TK_IgnoreUnlessSpelledInSource; + } +}; + +} // namespace performance +} // namespace tidy +} // namespace clang + +#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENTARRAYTRAVERSALCHECK_H diff --git a/clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.cpp b/clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.cpp new file mode 100644 --- /dev/null +++ b/clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.cpp @@ -0,0 +1,103 @@ +//===--- 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/AST/ASTContext.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/ASTMatchers/ASTMatchersInternal.h" +#include "clang/Basic/DiagnosticIDs.h" +#include "llvm/ADT/StringRef.h" + +using namespace clang::ast_matchers; + +namespace clang { +namespace tidy { +namespace performance { + +namespace { +AST_MATCHER_P(Stmt, hasSingleStmt, ast_matchers::internal::Matcher, + InnerMatch) { + clang::ast_matchers::internal::BoundNodesTreeBuilder Copy(*Builder); + if (InnerMatch.matches(Node, Finder, &Copy)) { + *Builder = Copy; + return true; + } + if (const auto *Res = dyn_cast(&Node)) { + return Res->size() == 1 && + InnerMatch.matches(*Res->body_front(), Finder, Builder); + } + return false; +} +ast_matchers::internal::Matcher +stmtOrCompound(ast_matchers::internal::Matcher Inner) { + return anyOf(Inner, compoundStmt(hasAnySubstatement(Inner))); +} +} // namespace + +static const char InnerVar[] = "InnerVar"; +static const char OuterVar[] = "OuterVar"; +static const char InnerLoop[] = "InnerLoop"; +static const char OuterLoop[] = "OuterLoop"; +static const char ArrayAccess[] = "ArrayAccess"; + +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())).bind(Var)))), + hasCondition(binaryOperator(hasEitherOperand(ToDecl))), + // TODO: Add support for x [+-]= 1 and x = x [+-] 1 + hasIncrement(unaryOperator(hasUnaryOperand(ToDecl), + hasAnyOperatorName("++", "--"))), + 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))); + Finder->addMatcher(NestedLoopMatcher(ArrayExprMatcher), this); + // TODO: Add a matcher that works on flattened arrays - + // Array[InnerVar * OuterExtent + OuterVar] + // TODO: Add a matcher that works for containers + // VectorOfVectors[InnerVar][OuterVar] +} + +void InefficientArrayTraversalCheck::check( + const MatchFinder::MatchResult &Result) { + const auto *Array = Result.Nodes.getNodeAs(ArrayAccess); + const auto *InnerLoopStmt = Result.Nodes.getNodeAs(InnerLoop); + const auto *OuterLoopStmt = Result.Nodes.getNodeAs(OuterLoop); + const auto *InnerVariable = Result.Nodes.getNodeAs(InnerVar); + const auto *OuterVariable = Result.Nodes.getNodeAs(OuterVar); + diag(Array->getBeginLoc(), + "Nonsequential array traversal can harm performance"); + diag(InnerLoopStmt->getBeginLoc(), "Row index %0 incremented in this loop", + DiagnosticIDs::Note) + << InnerVariable + << SourceRange(InnerLoopStmt->getBeginLoc(), + InnerLoopStmt->getRParenLoc()); + diag(OuterLoopStmt->getBeginLoc(), "Column index %0 incremented in this loop", + DiagnosticIDs::Note) + << OuterVariable + << SourceRange(OuterLoopStmt->getBeginLoc(), + OuterLoopStmt->getRParenLoc()); +} + +} // namespace performance +} // namespace tidy +} // namespace clang diff --git a/clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp b/clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp --- a/clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp +++ b/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( "performance-inefficient-algorithm"); + CheckFactories.registerCheck( + "performance-inefficient-array-traversal"); CheckFactories.registerCheck( "performance-inefficient-string-concatenation"); CheckFactories.registerCheck( diff --git a/clang-tools-extra/docs/ReleaseNotes.rst b/clang-tools-extra/docs/ReleaseNotes.rst --- a/clang-tools-extra/docs/ReleaseNotes.rst +++ b/clang-tools-extra/docs/ReleaseNotes.rst @@ -111,6 +111,12 @@ Reports identifier with unicode right-to-left characters. +- New :doc:`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 ` check. diff --git a/clang-tools-extra/docs/clang-tidy/checks/list.rst b/clang-tools-extra/docs/clang-tidy/checks/list.rst --- a/clang-tools-extra/docs/clang-tidy/checks/list.rst +++ b/clang-tools-extra/docs/clang-tidy/checks/list.rst @@ -273,6 +273,7 @@ `performance-for-range-copy `_, "Yes" `performance-implicit-conversion-in-loop `_, `performance-inefficient-algorithm `_, "Yes" + `performance-inefficient-array-traversal `_, `performance-inefficient-string-concatenation `_, `performance-inefficient-vector-operation `_, "Yes" `performance-move-const-arg `_, "Yes" diff --git a/clang-tools-extra/docs/clang-tidy/checks/performance-inefficient-array-traversal.rst b/clang-tools-extra/docs/clang-tidy/checks/performance-inefficient-array-traversal.rst new file mode 100644 --- /dev/null +++ b/clang-tools-extra/docs/clang-tidy/checks/performance-inefficient-array-traversal.rst @@ -0,0 +1,26 @@ +.. 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]++; + diff --git a/clang-tools-extra/test/clang-tidy/checkers/performance-inefficient-array-traversal.cpp b/clang-tools-extra/test/clang-tidy/checkers/performance-inefficient-array-traversal.cpp new file mode 100644 --- /dev/null +++ b/clang-tools-extra/test/clang-tidy/checkers/performance-inefficient-array-traversal.cpp @@ -0,0 +1,72 @@ +// 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; + +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 + + 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 + + // 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(); + } + } +} + +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]++; + } + } + // 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(); + } +}