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,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, + 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))); +} +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(*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(InnerLoop); + diag(InnerLoopStmt->getBeginLoc(), "Row index %0 incremented in this loop", + DiagnosticIDs::Note) + << Result.Nodes.getNodeAs(InnerVar) + << SourceRange(InnerLoopStmt->getBeginLoc(), + InnerLoopStmt->getRParenLoc()); + const auto *OuterLoopStmt = Result.Nodes.getNodeAs(OuterLoop); + diag(OuterLoopStmt->getBeginLoc(), + "Column index %0 incremented in this loop", DiagnosticIDs::Note) + << Result.Nodes.getNodeAs(OuterVar) + << SourceRange(OuterLoopStmt->getBeginLoc(), + OuterLoopStmt->getRParenLoc()); + }; + if (const auto *Array = + Result.Nodes.getNodeAs(ArrayAccess)) { + diag(Array->getBeginLoc(), + "Nonsequential array traversal can harm performance"); + DisplayLoops(); + return; + } + if (const auto *Array = + Result.Nodes.getNodeAs(StridedArrayAccess)) { + diag(Array->getBeginLoc(), + "Nonsequential array traversal can harm performance"); + DisplayLoops(); + return; + } + llvm_unreachable("Unhandled Match"); +} + +} // 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 @@ -115,6 +115,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 @@ -274,6 +274,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,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]++; 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,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]++; +}